Сравнение массивов больших размеров

[e2e4]

Maslov в сообщении #250281 писал(а):

e2e4 в сообщении #250279 писал(а):

Насчет того, что у Вас unicode - т.е. 16 бит на символ, так это процессору все-равно, он как минимум 16-битными операндами и оперирует.

Ну это Вы бросьте
Может оперировать с байтами - CMP AL,1
может со словами (16 бит) - CMP AX,1
может с двойными словами (32 бита) - CMP EAX,1

Блин, вот так всегда - пишешь одно, а подразумеваешь совсем другое. Сейчас перечитал свое заявление - действительно ерунда. На самом деле я имел ввиду следующее:
В данном конкретном случае компилятор и ассемблер, с высокой степенью вероятности, сгенерируют код, который записывает наш char в 16-битный (а еще более вероятно, в 32 битный) регистр целиком. Соответственно, 8 или 16 бит занимал наш символ, в данном случае - все равно (для времени исполнения).
А мое убеждение, что процессор в конце концов будет работать с 16 (или с 32) разрядным числом подтверждается фразой из "Intel® 64 and IA-32 Architectures Optimization Reference Manual", раздел "3.2 PROCESSOR PERSPECTIVES" (ну и банальной логикой - вряд ли процессоры настолько поумнели, что могут сами загрузить в AL один байт, в AH следующий, и скормить это все в Integer Unit (запараллелить два сравнения), а потом еще и разобрать, какой из байтов не прошел сравнение, и что делать дальше):

Intel® 64 and IA-32 Architectures Optimization Reference Manual писал(а):

Dependencies for partial register writes incur large penalties when using the
Pentium M processor (this applies to processors with CPUID signature family 6,
model 9). On Pentium 4, Intel Xeon processors, Pentium M processor (with
CPUID signature family 6, model 13), such penalties are relieved by artificial
dependencies between each partial register write. Intel Core Solo, Intel Core Duo
processors and processors based on Intel Core microarchitecture can experience
minor delays due to partial register stalls. To avoid false dependences from
partial register updates, use full register updates and extended moves.

Таким образом рекомендуется работать с целыми регистрами для избежания проблем с ложными взаимозависимостями при записи в половинные регистры.

А операнды инструкций, конечно, могут быть 8-битными.

-- Пт окт 09, 2009 13:04:17 --

Maslov писал(а):

Естественно, во всех случаях вариант с хэшами будет работать быстрее, но в связи с тем, что его немного сложнее реализовать, я бы сначала все таки проверил работу напрямую со строками - может быть и в этом случае скорости окажется достаточно.

1. Не во всех, а только когда длина строки сильно больше длины хэша .
2. По сложности реализации я как раз уверен в обратном - реализация простейшей контрольной суммы (а ее тут ИМХО вполне достаточно) - значительно проще, чем, даже, сортировка пузырьком. А тут, конечно, надо что-то побыстрее, чем сортировка пузырьком.

[ewert]

e2e4 в сообщении #250351 писал(а):

1. Не во всех, а только когда длина строки сильно больше длины хэша

Если строки заполнены абсолютно случайно, то в качестве хэша вполне достаточно использовать первое слово или двойное слово. Т.е., фактически, вообще не использовать хэш.

[e2e4]

PAV писал(а):

Если задача прикладная и одноразовая, а цена вопроса, как тут посчитали - секунд 10 работы, то можно совершенно спокойно писать самый простейший лобовой алгоритм за 5-10 минут и переходить к другим задачам.

Самое главное, PAV, что простейший "лобовой" алгоритм в данном случае - наиболее надежен. Это зачастую гораздо важнее, чем время выполнения. Я очень часто вынужден писать неоптимальный код именно потому, что мне нужно, чтобы он заработал с первого раза. К сожалению (из-за нашей бедности и пофигизма) очень часто отладка программы происходит на рабочем, полноразмерном объекте вместо стенда. Ну и одна ошибка может привести к аварии на тысячи и десятки тысяч долларов, срыву сроков и т.п. А программист всего-то, может быть, в знаке или скобочке ошибся .

-- Пт окт 09, 2009 13:12:01 --

ewert в сообщении #250355 писал(а):

e2e4 в сообщении #250351 писал(а):

1. Не во всех, а только когда длина строки сильно больше длины хэша

Если строки заполнены абсолютно случайно, то в качестве хэша вполне достаточно использовать первое слово или двойное слово. Т.е., фактически, вообще не использовать хэш.

Т.е. использовать сравнение "в лоб" , что и требовалось доказать

[Maslov]

e2e4 в сообщении #250357 писал(а):

Самое главное, PAV, что простейший "лобовой" алгоритм в данном случае - наиболее надежен.

Вариант с сортировкой строк от лобового по сложности не сильно отличается - на пару строк всего, а выигрыш по времени может дать весьма существенный. Просто Вы предлагали не просто "в лоб", а еще и распараллелить на 4 машины/процессора, а это уже - существенное усложнение и, следовательно, источник потенциальных ошибок.

ewert в сообщении #250355 писал(а):

Если строки заполнены абсолютно случайно, то в качестве хэша вполне достаточно использовать первое слово или двойное слово. Т.е., фактически, вообще не использовать хэш.

Мне кажется, это не очень хороший способ:
1. Судя по всему, это практическая задача, а в таких задачах обычно не бывает абсолютно случайных строк.
2. Использование начального фрагмента строки в качестве хэша выигрыша не даст, т.к. если строки различаются в этом фрагменте, то и побайтовое сравнение будет очень быстрым, а если - не различаются, все равно придется сравнивать остаток строки побайтовым сравнением.

-- Пт окт 09, 2009 13:29:39 --

ewert в сообщении #250355 писал(а):

В данном конкретном случае компилятор и ассемблер, с высокой степенью вероятности, сгенерируют код, который записывает наш char в 16-битный (а еще более вероятно, в 32 битный) регистр целиком. Соответственно, 8 или 16 бит занимал наш символ, в данном случае - все равно (для времени исполнения).

Это так, но юникодные строки обрабатываются дольше "байтовых" не только из-за длины, там еще сравнение сложнее, т.к. двоичное представление символа не связано напрямую с его порядком при сортировке.

[e2e4]

Maslov писал(а):

Просто Вы предлагали не просто "в лоб", а еще и распараллелить на 4 машины/процессора, а это уже - существенное усложнение и, следовательно, источник потенциальных ошибок.

Никогда. Я предлагал, как вариант, задействовать дополнительные ядра (если она есть в вашем процессоре) более-менее стандартными средствами без изменения кода вообще.
И потом - я не агитирую за сравнение "в лоб", я просто хотел показать подход.

Maslov писал(а):

Это так, но юникодные строки обрабатываются дольше "байтовых" не только из-за длины, там еще сравнение сложнее, т.к. двоичное представление символа не связано напрямую с его порядком при сортировке.

А речь о сортировке не шла. Вспомните, мы об этом говорили, когда прикидывали время выполнения несортированного сравнения.

[ewert]

Maslov в сообщении #250358 писал(а):

Использование начального фрагмента строки в качестве хэша выигрыша не даст,

Именно об этом и речь. Но тогда и никакой хэш не даст выигрыша -- в том непрактичном случае, когда строчки случайны.

Maslov в сообщении #250358 писал(а):

, т.к. двоичное представление символа не связано напрямую с его порядком при сортировке.

Это был не я, но у меня всё равно вопрос. При чём тут юникод и вообще алфавит, если строчки всё равно сортируются по двоичному коду?

[Lotos]

Все это очень воодушевило на творческий процесс.
Привет, коллеге по учебному процессу.
Это не учебная программа, просто кушать хочется

[Maslov]

ewert в сообщении #250361 писал(а):

Именно об этом и речь. Но тогда и никакой хэш не даст выигрыша -- в том непрактичном случае, когда строчки случайны.

В случае абсолютно случайных строк хэш действительно не дает никакого выигрыша, но на практике в большинстве случаев оказывается весьма эффективным

ewert в сообщении #250361 писал(а):

При чём тут юникод и вообще алфавит, если строчки всё равно сортируются по двоичному коду?

Это зависит от среды исполнения. Если строки юникодные (как, например, в Java или в .Net), сравнение строк, а, следовательно, и сортировка, возвращает результат <,=,> именно в соответствии с алфавитным порядком. И в этом случае возможны довольно экзотические варианты, например, в датском языке 'å' = 'aa', и операция сравнения строк обязана это учитывать.

-- Пт окт 09, 2009 13:58:01 --

e2e4 в сообщении #250360 писал(а):

А речь о сортировке не шла. Вспомните, мы об этом говорили, когда прикидывали время выполнения несортированного сравнения.

Сравнивать-то строки все равно приходится, а сравнение по тем же правилам выполняется.

-- Пт окт 09, 2009 13:59:35 --

e2e4 в сообщении #250360 писал(а):

я просто хотел показать подход

Тут Вы абсолютно правы. В первую очередь надо искать под фонарем (это я безо всякой иронии говорю).

[Pavia]

Я бы начал с std где сортировка строк уже сделана через хэши.

[venco]

PAV в сообщении #250311 писал(а):

venco в сообщении #250267 писал(а):

Если бы я учил программированию, и мне кто-нибудь из учеников принёс программу, которая вместо предполагаемых секунд работает час из-за неэффективного алгоритма, я бы в лучшем случае поставил тройку за то, что хоть какой-то результат есть.

Хорошо видно типичное отличие учебного подхода от промышленного. Если задача прикладная и одноразовая, а цена вопроса, как тут посчитали - секунд 10 работы, то можно совершенно спокойно писать самый простейший лобовой алгоритм за 5-10 минут и переходить к другим задачам.

Я как раз профессиональный программист. В данном случае оба способа пишутся в несколько строк, причём способ с set<> будет самым коротким и простым. Способ с сортировкой лишь чуть сложнее, но он может не подойти, т.к. один из массивов придётся изменять. Двойной цикл же не только самый неэффективный, но ещё и больше подвержен ошибкам.

[ewert]

venco в сообщении #250385 писал(а):

Способ с сортировкой лишь чуть сложнее, но он может не подойти, т.к. один из массивов придётся изменять.

Зачем? Достаточно сортировать указатели на строки. Всё равно ведь мы собираемся завести массив хэшей, так пусть там же хранятся заодно и указатели.

[Maslov]

ewert в сообщении #250387 писал(а):

Зачем? Достаточно сортировать указатели на строки. Всё равно ведь мы собираемся завести массив хэшей, так пусть там же хранятся заодно и указатели.

Правильно, правильно. Указатели или индексы.

-- Пт окт 09, 2009 15:10:16 --

По поводу "типичного отличия учебного подхода от промышленного": пока никакого отличия нет. Как при учебном, так и при промышленном подходе реализации задачи предшествует анализ возможных вариантов ее решения. Чем мы тут, собственно, и занимаемся. Согласен - занимаемся довольно долго, но это особенность форумного стиля, а не "учебного" подхода.
При этом анализ вариантов осуществляется в условиях недостаточной информации: задача явно является частью какой-то более общей задачи, о которой вообще ничего не известно.

-- Пт окт 09, 2009 15:26:26 --

А основной признак "учебного" подхода - это, как мне кажется, принцип "сдал - забыл". И от этого приходится отучать вчерашних студентов. Потому как практически все, что сдано, еще и сопровождать приходится

[e2e4]

Цитата:

ewert писал(а):

При чём тут юникод и вообще алфавит, если строчки всё равно сортируются по двоичному коду?

Это зависит от среды исполнения. Если строки юникодные (как, например, в Java или в .Net), сравнение строк, а, следовательно, и сортировка, возвращает результат <,=,> именно в соответствии с алфавитным порядком. И в этом случае возможны довольно экзотические варианты, например, в датском языке 'å' = 'aa', и операция сравнения строк обязана это учитывать.

Теперь я чего-то непонимаю. Зачем нам какие-то алфавиты, если для сравнения строк достаточно равенства кодов входищих в эти строки символов? Просто char - это 8 бит обычно, а unicode - 16 бит. Сравнение - это вычитание кода одного символа из кода другого. Результат вычитания ноль - следовательно символы равны. Нет?

В общем этта. Потестировал. Среда: Borland Builder 6.0, полная оптимизация, генерируемый код - под Pentium Pro, среда - Windows XP Home SP2, процессор - Pentium M 740@1.73 Ghz@7 400 MIPS, % загрузки процессора программой - около 96%.
Основной код:

#include <vcl.h>
#include "Unit1.h"
#include "time.h"
#include "math.h"
#include "string.h"

....

void __fastcall TForm1::Button1Click(TObject *Sender)
{
   static char str[2][50000][256];
   int eq_n = 0;

/* Последний символ строки - рэндом, остальные - 0x00 (массив static, инициализируется автоматически).
Просто так, чтобы программа хоть какой-то результат выводила. */
   for (int k = 0; k < sizeof(str)/sizeof(str[0]); k++)
      for (int i = 0; i < sizeof(str[0])/sizeof(str[0][0]); i++)
         str[k][i][sizeof(str[0][0])/sizeof(str[0][0][0]) - 1] = rand()%0xFF;  

   time_t t1,t2;

   t1 = time(NULL);  //Засекаем время в сек.

   for (int i = 0; i < 26000; i++) 
   {
      for (int j = 0; j<16000; j++)
         if(!memcmp(str[0][i], str[1][j], sizeof(str[0][0])/sizeof(str[0][0][0]))) eq_n++; //Ура, совпало
      if (i % 100 == 0) {Label3->Caption = AnsiString (i); Form1->Update();} //Чтобы видеть прогресс задачи
   }

   t2 = time(NULL);
   Label1->Caption = AnsiString(t2-t1);  //Просто вывод на экран времени выполнения
   Label2->Caption = AnsiString(eq_n);  //Просто вывод на экран кол-ва совпавших строк.
}

Результаты:
1. Основной потребитель времени - функция memcmp. Прочие расходы на циклы, вывод на экран и т.п. пренебрежительно малы (<5%).
1. Функция memcmp работает в 2,5 раза быстрее strncmp, и на 15% быстрее, чем если крутить третий цикл и просто сравнивать байты (оба этих результата меня лично удивили - т.е. я не ожидал что с strncmp все так плохо, а с ручным циклом все так хорошо).
2. Массив 26 000 х 16 000 выполняется за 3,3 мин
3. Массив 50 000 х 50 000 выполняется за 20 мин

[ewert]

e2e4 в сообщении #250412 писал(а):

я не ожидал что с strncmp все так плохо,

Так она ведь делает в цикле не одну проверку, как memcmp (на счётчик цикла), а три -- в дополнение ещё и проверяет, не наткнулись ли мы на конец хотя бы одной из двух строк.

[Maslov]

e2e4 в сообщении #250412 писал(а):

Теперь я чего-то непонимаю. Зачем нам какие-то алфавиты, если для сравнения строк достаточно равенства кодов входищих в эти строки символов? Просто char - это 8 бит обычно, а unicode - 16 бит. Сравнение - это вычитание кода одного символа из кода другого. Результат вычитания ноль - следовательно символы равны. Нет?

Не совсем
В Java и .Net все строки юникодные, и операция сравнения строк сравнивает их именно как последовательности юникодных символов, а не как байтовые массивы. И так же, как в случае memcmp, результат операции - это не "да"/"нет", а "< 0"/" == 0"/"> 0", при этом символы сравниваются в лексикографическом порядке, а не в порядке следования их двоичных кодов. В большинстве случаев эти порядки совпадают, но не всегда. А уж используется там кодировка UTF-16 (16 бит) или UTF-32 (32 бит) - это вообще мало кому интересно и зависит только от конкретной реализации.