Теперь мой реальный вопрос: как я могу иметь такую же эффективность по времени, НО без использования какого-либо преобразования в мой массив?
Я не верю, что приведение в C имеет штраф за время выполнения. Все в C все равно число. Я считаю, что это просто говорит компилятору, что да, вы знаете, что используете неправильный тип, и считаете, что это нормально.
Обратите внимание, что char может быть подписано. В него может проникнуть отрицательное число.
Эта программа работает как O (m * n), где m - наша первая строка, а n - наша вторая строка.
Нет, он работает как O (n). O (m * n) было бы, если бы вы перебирали одну строку для каждого символа другого.
for( int i = 0; i < strlen(str1); i++ ) {
for( int j = 0; j < strlen(str2); j++ ) {
...
}
}
Но вы перебираете каждую строку одну за другой в двух независимых циклах. Это O (m + n), то есть O (n).
На улучшениях. Во-первых, temp нужно только удерживать диапазон char, который, самое большее, 256. Давайте дадим ему имя переменной, которая описывает, что она делает, chars_seen.
Наконец, нет необходимости хранить полное целое число. Обычно мы использовали бы bool из stdbool.h, но мы можем определить наше собственное, используя signed char, что, вероятно, и сделает stdbool.h. Мы обязательно завернем его в #ifndef bool, поэтому мы будем использовать поставляемую систему, если она доступна, она будет знать лучше, чем мы, какой тип использовать для логического значения.
#ifndef bool
typedef signed char bool;
#endif
bool chars_seen[256] = {0};
Возможно, вам удастся повысить производительность, исключив i и вместо этого непосредственно увеличивая указатель. Это не только повышает производительность, но и упрощает многие операции со строками и массивами.
for( ; *str != '\0'; str++ ) {
if( !chars_seen[(size_t)*str] ) {
chars_seen[(size_t)*str] = 1;
write(1, str, 1);
}
}
Обратите внимание, что я преобразую в size_t, а не int, потому что это правильный тип для индекса.
Возможно, вы сможете побриться, используя постинкремент, будет ли эта помощь зависеть от вашего компилятора.
if( !chars_seen[(size_t)*str]++ ) {
write(1, str, 1);
}
Наконец, чтобы избежать повторения вашего кода и расширить его для работы с любым количеством строк, мы можем написать функцию, которая принимает набор видимых символов и отображает одну строку. И мы дадим компилятору подсказку встроить его, хотя это сомнительно.
inline void display_chars_no_dups( const char *str, bool chars_seen[]) {
for( ; *str != '\0'; str++ ) {
if( !chars_seen[(size_t)*str]++ ) {
write(1, str, 1);
}
}
}
Затем main выделяет массив видимых символов и вызывает функцию столько раз, сколько необходимо.
int main(int argc, char *argv[]) {
bool chars_seen[256] = {0};
for( int i = 1; i < argc; i++ ) {
display_chars_no_dups( argv[i], chars_seen );
}
write(1, "\n", 1);
}