За время, прошедшее с последнего поста, количество просмотров этой темы увеличилось еще на 10 тысяч, а общее количество просмотров перевалило при этом за 60 тысяч - умопомрачительная цифра для этого и других форумов Интел! И вот за это время поднакопился новый материал – конкурс-то идет своим ходом:
Во-первых, в шестом туре премию ожидаемо получило решение, сообщающее правильный или НЕправильный результат в зависимости от исходных данных - т.е. решение не совсем неправильное, а только частично – иногда оно все же дает и правильные ответы, можно только удивляться, что все 4 или 5 теста судей (или по-прежнему одного судьи?) такие, что ответ получается правильный и, естественно, самый быстрый. А что при беглом взгляде на алгоритм видно, что он не правильный, это никого, или почти никого, не взволновало (если не считать многочисленные посты участников на американском форуме). Впрочем, об этом уже и на этом форуме был небольшой обмен мнениями.
Во-вторых, в теперешнем седьмом туре судьи (судья?) решили (решил?) наступить еще раз на грабли первого тура (go on:)) и оценить быстродействие сортировки – в первом туре была «быстрая» сортировка, в этом сортировка «слиянием» - совместно с быстродействием ввода-вывода. Я, к примеру, получил следующие результаты: CPU Pentium-4 3.0 GHz, OS MS Windows XP SP 2, размер файла 2^26 целых чисел :
- время, потраченное на чтение данных из входного файла 75 сек., время на сортировку 23 сек., время на запись 78 сек., (общее время 176 сек.).
А для другого жесткого диска и для другой копии Windows XP на том же компьютере я получил:
- время, потраченное на чтение данных из входного файла 30 сек., время на сортировку 22 сек., время на запись 141 сек., (общее время 193 сек.).
Можно начать сортировку, и не дожидаясь окончания чтения, - как только количество прочитанных данных достигнет объема, выделенного очередному потоку сортировки, – тут же этот поток запускать. Я попробовал, и получил общее время 154 сек. Кроме того, можно совместить финальное объединение отсортированных данных с выводом в файл – попробовал – получил 144 сек.
Очевидно, что для многоядерных CPU и для лучшей оптимизации алгоритма сортировки
различие между временем сортировки и временем на ввод-вывод будут еще значительней!
Что же показывают полученные результаты? А показывают они, что время работы программы (единственная, казалось бы, объективная характеристика решения, не зависящая от судейского произвола) при данной постановке задачи прежде всего зависит от размера файла, от физических характеристик диска (время доступа и т.д.), от формата диска (FAT, NTFS, Linux форматы и т.д.), от истории диска (его фрагментации), а также от времени, идущего на процедуры стандартного ввода-вывода, которое скорее всего различно для разных компиляторов. И ТУТ МЫ ВОЗВРАЩАЕМСЯ К ТЕМЕ ДАННОГО СООБЩЕНИЯ в ее новой интерпретации – речь идет уже не только о языковой дискриминации, но о системной и компиляторной дискриминации! Теперь и С++ достанется – не факт, что все его I/O процедуры во всех компиляторах работают быстрее всех прочих компиляторов всех прочих языков. Прежде всего, у Юрия как разработчика МС#, появляется реальный шанс сделать специфически быструю процедуру заглатывания больших кусков текстового файла, состоящего из беззнаковых целых чисел по числу в строке… Остальные участники тоже могут оптимизировать свои решения под определенные размеры файлов, типы жестких дисков, и также могут попробовать заменить стандартные процедуры ввода-вывода на оригинальные ;) можно также попробовать организовать параллельное чтение разных кусков входного файла из потоков, рассматривая текстовой файл последовательного доступа как двоичный файл с произвольным доступом. Однако возникает вопрос: действительно ли оптимизация ввода-вывода является основной целью данного задания?
Кроме того, решение оптимальное под один тип дисков и под один размер файлов будет явно не оптимальным под другой тип дисков и другой размер входного файла :(
Пока с этим конкурсом перманентно продолжаются вышеуказанные перманентные заморочки, я решил мультипоточно попробовать другой конкурс Интел, тоже мультипоточный – может, старейшая игра в мультипоточном режиме будет успешнее – прочитать про нее и проголосовать за :) или против :( нее можно по ссылке: http://softwarecontests-rus.intel.com/gamedemo/entrydetail.php?entryid=95
-- Михаил (mt2)
