Сравнение чисел быстрее, чем сравнение строк?
Я слышал, что хеширование (то есть преобразование строки или объекта в число) используется для строк и потому, что сравнивать числа легче, чем строки. Если это правда, что является причиной этого?
Решение
Это не обязательно так, но, вероятно, так происходит большую часть времени.
Рассмотрим следующую ситуацию:
Я хочу сравнить строку «яблоки» против «апельсины». Если я хочу определить только «яблоки» == «апельсины», мне нужно сравнить только первый символ каждой строки: «a»! = «O» => «яблоки»! = «Апельсины». Если я хеширую строку, а затем выполняю сравнение, это значительно медленнее, так как мне приходится анализировать обе строки и передавать их в алгоритм хеширования перед сравнением результирующих целых чисел.
Однако если мне нужно сделать это сравнение много раз, и, возможно, я много сравниваю «апельсины» с «орангутангами», то, если я хеширую все строки один раз и многократно сравниваю целые числа, это сработает Быстрее. Это принцип, на котором основана хеш-карта.
Обратите внимание, однако, что хеширование строки полезно для прямых сравнений, оно не может определить, являются ли строки лексографически большими или меньше друг друга, и поэтому упорядочивание строк невозможно с помощью метода хеширования. (Вот почему HashMap в Java неупорядочен).
Другие решения
Сравнение двух чисел — это величины быстрее, чем сравнение двух строк (представляющих одинаковые числа). Сравнение двух чисел просто требует сравнения отдельных битов и может быть сделано очень быстро с использованием любого из AND, XOR, дополнений 2 и т. Д.
Сравнение двух строк очень медленное и дорогое. Большинство алгоритмов требуют итерации всей строки и сопоставления каждого символа.
Например, скажем, мы хотим сравнить 9 с 12 (ложь). Для числового сравнения предположим, что алгоритм сравнивает отдельные биты.
9 = 1001
12 = 1100
Здесь алгоритм наихудшего случая будет сравнивать 4 бита.
Теперь, если мы представим «9» и «12» как строки, они будут сохранены в памяти как 16 бит каждая (Напомним: Java использует UTF-16 для представления строк в памяти) и должны быть переданы в алгоритм сравнения строк. Фактически, фактическая функция сравнения строк в Java приведена ниже:
public boolean equals(Object anObject) {
if (this == anObject) {
return true;
}
if (anObject instanceof String) {
String anotherString = (String)anObject;
int n = count;
if (n == anotherString.count) {
char v1[] = value;
char v2[] = anotherString.value;
int i = offset;
int j = anotherString.offset;
while (n-- != 0) {
if (v1[i++] != v2[j++])
return false;
}
return true;
}
}
return false;
}
Как вы можете видеть, для сравнения строк гораздо больше.
Сравнение примитивных чисел определенно быстрее, чем сравнение строк, потому что это всего лишь одна компьютерная инструкция, а сравнение строк в Java — это метод. Но хеширование в Java используется по другой причине, Object.hashCode () используется в хеш-таблицах для быстрого поиска в коллекциях.
Как правило, большинство компьютеров имеют одну инструкцию для сравнения целых, длинных и т. Д.
и займет не более пары учебных циклов. Строки обычно сравниваются служебной функцией / методом (может быть странное исключение из этого правила).
в Java, например, строка в основном представлена как
/** The value is used for character storage. */
private final char value[];
/** The offset is the first index of the storage that is used. */
private final int offset;
/** The count is the number of characters in the String. */
private final int count;
И метод равно
if (this == anObject) {
return true;
}
if (anObject instanceof String) {
String anotherString = (String)anObject;
int n = count;
if (n == anotherString.count) {
char v1[] = value;
char v2[] = anotherString.value;
int i = offset;
int j = anotherString.offset;
while (n-- != 0) {
if (v1[i++] != v2[j++])
return false;
}
return true;
}
}
return false;
Метод equals делает оба this == anObject а также n == anotherString.count, оба по существу целочисленные сравнения, даже до того, как он начинает сравнивать символы. Это займет намного больше времени, чем одна инструкция, которая занимает целочисленное сравнение.
Сравнение строки C является проще / быстрее чем эквивалент Java, но он будет содержать своего рода цикл и несколько инструкций для каждого прохождения цикла.
Это займет больше времени, чем одна инструкция, которую требует Integer Compare
Да, но это не имеет ничего общего с хешированием.
Сравнение чисел включает в себя простые аппаратные инструкции, которые сравнивают биты.
Сравнение строк включает в себя (а) итерацию по обеим строкам до тех пор, пока вы не найдете отличающиеся символы (в отличие от чисел, которые имеют фиксированный размер) и (б) много магии Юникода (разные строки разной длины могут фактически быть равными, а разные символы в разном коде блоки сравнивают по разному).
Хеширование обычно используется для преобразования строки в индекс массива.