[LinuxWorld 2005] Конкурс от Sun microsystems на самую быструю программу

durka82

Вот, попросили опубликовать:
До сих пор помните чем пузырьковая сортировка отличается от пирамидальной ?
Все еще используете xor %ax, %ax вместо mov $0, %ax ?
Дискетку с демой для ZX Spectrum храните под стеклом ?
Если хотя бы на один из этих вопросов вы ответили "да", тогда у вас есть
шанс выиграть рабочую станцию Sun Java Workstation W1100z.
Правила очень просты: от вас требуется разработать самую быструю программу,
работающую под ОС Linux, которая бы считывала алфавитно-цифровые строки со
стандартного входа и выдавала 1000 наибольших (с точки зрения лексикографической
сортировки) строк на свой стандартный выход. Проще говоря, мы предлагаем вам
написать приложение, которое делает тоже самое, что и следующая комбинация
команд:
$ sort | tail -1000
и при этом работает быстрее всех!
Для участия в конкурсе, необходимо просто придти к нам в гости на выставку
LinuxWorld 2005, проводимую в Москве с 7го по 9ое сентября и найти павильон
компании Sun microsystems. Отдать сотрудникам проекта Sun Studio исходный код
на любом языке программирования, компилятор (или интерпретатор!) для которого
содержится в стандартном дистрибутиве SuSE Professional 9.3, а так же
инструкции по построению и запуску вашей программы.
Победителем конкурса и обладателем рабочей станции Sun Java Workstation W1100z,
станет тот, чья программа не только выдаст правильный результат на трех заранее
подготовленных файлах, но так же опередит всех остальных участников конкурса
по времени исполнения! Предупреждаем, что в числе участников конкурса уже
есть реализация выигравшая в Сан-Франциско -- так что конкуренция
будет серьезная.
Подведение итогов и объявление победителя произойдет в 15 часов по московскому
времени 9го сентября в павильоне компании Sun microsystems. Тогда же состоится
разбор полетов и раздача утешительных призов !
В заключении несколько слов для тех, кто просто хочет пообщаться с инженерами
проекта Sun Studio или же вообще не знает о том, как попасть на конференцию
LinuxWorld 2005 -- не забудьте зарегистрироваться на официальном сайте
конференции по адресу:

http://www.linuxworldexpo.ru/ticket.en.html
Регистрация абсолютно БЕСПЛАТНА!
п.с.: а в ФДС этот форум читают?

qsk78

п.с.: а в ФДС этот форум читают?

читают

durka82

Добавление:
Место: выставочный комплекс "Гостиный Двор" (ул. Ильинка, 4)
Время работы:
Среда: 10:00-17:00
Четверг: 10:00-17:00
Пятница: 10:00-16:00
К сожалению, бесплатная регистрация на конференцию закончилась.
Вниманию студентов! Поскольку бесплатная регистрация закончилась, вы можете посетить выставку LinuxWorld каждый день в последний час работы выставки. При регистрации на входе необходимо предъявить ваш студенческий билет!
7 и 8 сентября вы можете отдать свои решения на дискете представителям компании Sun Microsystems.

fortuna77-90

А ежели не студент?

durka82

Интересует цена билета?
И не аспирант/преподаватель?

bel23

см. http://www.linuxworldexpo.ru/visitors.ru.html
"Вход на выставку строго по пригласительным билетам, визитным карточкам или предварительной регистрации на веб-сайте. "
Cудентов еще в последний час пускают
Ежели не студент, можно попробовать пробраться в последний час работы выставки

Кстати, кто там был - расскажите о впечатлениях

Olyalyau

А где вывесят код самых быстрых? Очень хочется глянуть.
Моя прога строк в 30 обгоняет sort | tail -1000 раз в восемь.
Жаль, что не удастся сходить на LinuxWorld и поучаствовать.
PS.
sort не сортирует строки в лексикографическом порядке.
Наблюдаем:



$ echo -en "  \n1\n 2\n" | sort

   

1

 2

$

Первая строка после сортировки содержит два пробела, вторая "1", третья пробел и "2".
В лексикографическом порядке (в ASCII ' ' < '1' < '2') будет:

Dasar

если твоей программе дать террабайтный файл с гиговыми строчками - она работать сможет?

Olyalyau

Она может работать с любыми файлами, которые sort | tail -1000 переваривает.
Если на какой-то платформе он переваривает терабайтовые файлы с гигабайтовыми строчками, моя прога
тоже на этой платформе их обработает.

Dasar

sort тоже, что ли, весь файл в память тянет?

Olyalyau

sort тоже, что ли, весь файл в память тянет?

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

Правила очень просты: от вас требуется разработать самую быструю программу,
работающую под ОС Linux, которая бы считывала алфавитно-цифровые строки со
стандартного входа и выдавала 1000 наибольших (с точки зрения лексикографической
сортировки) строк на свой стандартный выход.

по условию ни какого файла нет, есть только стандартный вход.
Так как в стандартном потоке входа нельзя делать свободно lseek, никуда не денешься от больших трат памяти.
Методом "записать сначала стандартный вход в файл" можно, конечно, свести задачу к предыдущей. Но никто не обещал, что хоть куда-то разрешена запись. Кроме того, этим методом можно добиться работы программы в тех редких случаях, когда кому-то надо отсортировать что-то очень большое, только за счёт падения производительности во всех случаях.

karkar

Сдаеца мне, что там будут рулить хитрые алггоритмы сравнения строк. Тут одних знаний сортировок недостаточно. Всякие суффиксные деревья и массивы ботать надо..

Olyalyau

суффиксные деревья

Ты хочешь сказать префиксные.
Не думаю. Хотя можно попробовать сделать на префиксном дереве и посмотреть, станет ли быстрее.
Префиксные деревья могут помочь разве что от падения производительности в тех редких случаях,
когда большинство строчек начинается на один и тот же префикс.

Dasar

для больших файлов - еще будут рулить хитрые алгоритмы аллокации строк.

bleyman

Ещё тут будет рулить ограничение в 1000 строк. Ну то есть хранить больше тысячи строк ведь не нужно.

Olyalyau

Ну так что, где вывешен код самых-самых?
Посмотреть хочется.

procenkotanya

Да, я там был, мёд-пиво пил %)

Моя прога строк в 30 обгоняет sort | tail -1000 раз в восемь.
Жаль, что не удастся сходить на LinuxWorld и поучаствовать.

Хм, стоило сходить. Если я ничего не путаю, прога Sun Microsystems тоже где-то в 8 раз быстрее этого конвейера, так что ты бы составил неплохую конкуренцию. Кстати, нельзя ли код в студию или мне в ПМ, пожалуйста?

sort не сортирует строки в лексикографическом порядке.

man sort %) Лучше

 LC_ALL=C sort|tail -1000

Ну так что, где вывешен код самых-самых?
Посмотреть хочется.

Обещали выложить на http://developers.sun.com/sunstudio/linux , но, по правде говоря, смотреть-то и не на что. На выставке сказали, что в Сан-Франциско пришёл только один человек; у нас пришло с десяток, только пять прог правильно работали на элементарных тестах, только две в итоге за разумное время переварили тесты Sun (если время, которое тратит sort|tail + 10 секунд не считать разумным, то только одна).

Кстати, кто там был - расскажите о впечатлениях

Неплохо там. Приезжал Джон maddog Холл (правда, послушать его мне не довелось). Были представители ReactOS. LinuxCenter продавал дистры и всякие футболочки, кепочки. Кстати, стенд Sun Microsystems был украшен программой-полиглотом - прогой на 8 языках сразу: см. http://ideology.com.au/polyglot/

rosali

Предупреждаем, что в числе участников конкурса уже
есть реализация выигравшая в Сан-Франциско -- так что конкуренция
будет серьезная.

в Сан-Франциско пришёл только один человек

Я щас абассусь!

Kalya777

Да, борьба за приз была нешуточная

laki

Серьезная конкуренция

Olyalyau

Простейший код:



#include <limits>

#include <iostream>

#include <string>

#include <set>

#include <algorithm>

#include <iterator>

                                                                                                                        

using namespace std;

                                                                                                                        

int

main 

{

  string                str;

  char                  ignore (numeric_limits <char>::min ;

  unsigned int const    number (1000);

  multiset <string>     greatest;

                                                                                                                        

  while (getline (cin, str

  {

    if (str [0] < ignore)

      continue;

                                                                                                                        

    greatest.insert (str);

                                                                                                                        

    if (greatest.size  > number)

    {

      greatest.erase (greatest.begin ;

      ignore = (* greatest.begin  [0];

    }

  }

                                                                                                                        

  copy (greatest.begin  greatest.end  ostream_iterator <string> (cout, "\n";

}

Алгоритм асимптотически линейный по количеству строк. У sort'а не может лучше $O(n\ln(n$
(и не должно быть сильно хуже). Так что, степень обгона измеряется только количеством строк в
std::cin.
Падение скорости на файле, содержащем sed -e 's/^/a/g' от файла ~900Mb не превысило 20%,
так что с префиксными деревьями я не стал заморачиваться -- падение скорости из-за сложности кода будет больше 20%. Хотя, конечно RB-tree, используемое в моём коде, тоже не подарок.

procenkotanya

Спасибо, что ответил.
Не обижайся, но про восемь раз ты сильно загнул (тестовый пример, видимо, совсем хороший попался). На тестах, что использовались на конкурсе (и, кстати, на тестах, которые я использовал при отладке своей проги ты заметно отстаёшь от конвейера sort|tail

.
Да, кстати, в Sun'овских тестах есть длинные одинаковые префиксы.

Olyalyau

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

Olyalyau

тестовый пример, видимо, совсем хороший попался

Мой стандартный тестовый пример:
find /usr/share/doc -type f -exec cat \{\} \; > Example

Papazyan

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

procenkotanya

тесты Sun
переименуй в .tar.bz2

procenkotanya

Ты это о чём? У Серёжи такая оптимизация есть.

Papazyan

Я не заметил

Dasar

> Хотя, конечно RB-tree, используемое в моём коде, тоже не подарок.
вообще-то, по идее, т.к. есть ограничение на 1000 - можно сгенерить таблицу для идеальной сортировки
ps
вот только с ходу не могу вспомнить оценку размера такой таблицы.

Olyalyau

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

Как я уже писал,

Падение скорости на файле, содержащем sed -e 's/^/a/g' от файла ~900Mb не превысило 20%

Команда sed -e 's/^/a/g' вставляет в каждую строку первым элементом символ 'a', после чего логика с проверкой первого символа (str [0] < ignore) перестаёт помогать. И из-за этого скорость падает не больше, чем на 20% (в моих тестах). А вообще, профайлер (gprof) показывает, что порядка 90% времени программа проводит в функции main . То есть, как раз в цикле и на проверках (str [0] < ignore а не на работе с деревом (insert/erase).

Dasar

плохой вариант для своей программы знаешь? ты его гонял? на профайлере смотрел?

Papazyan

Вообще, думаю, рулит самая тупая стратегия. Типа этой



#include <stdio.h>

#include <stdlib.h>

#include <string.h>

void oops(void) {

	printf("No memory of something like this\n");

	exit(1);

}

char* read_string(void) {

	int i = 0;

	int c;

	char* str = NULL;

	/* we have just 1000 strings, so it's ok */

	int power = 1024;

	if str = (char*)malloc(power+1 == NULL)

		oops;

	

	while c = getchar != EOF) {

		if char)c == '\n') break;

		str[i++] = (char)c;

		

		/* buffer overflow */

		if (i >= power) {

			char* n_str;

			if n_str = (char*)malloc(2*power+1 == NULL)

				oops;

			

			memcpy(n_str, str, power);

			free(str);

			str = n_str;

			power *= 2;

		}

	}

	if i == 0)&&(c == EOF return NULL;

	str[i] = 0;

	return str;

}

/* order: 1000 < 0 */

char* strs[1000];

inline void shift_array(char* str, int pos) {

	int i;

	/* remove the last element */

	free(strs[999]);

	/* shift the array */

	for (i = 998; i >= pos; i--)

		strs[i+1] = strs[i];

	strs[pos] = str;

}

inline int str_less(char* a1, char* a2) {

	int i = 0;

	while (1) {

		if (a1[i] < a2[i])

			return 1;

		if (a1[i] > a2[i])

			return -1;

		if (a1[i] == 0) 

			return 0;

		i++;

	}

}

void print_result(int limit) {

	int i;

	for (i = limit; i > 0; i--)

		printf("%s\n", strs[i-1]);

}

void insert_raw(char* str) {

	int dup = 999;

	int ddown = 0;

	int d = 0;

	int res;

	if (str_less(str, strs[999]) >= 0) {

		free(str);

		return;

	}

	if (str_less(strs[0], str) >= 0) {

		shift_array(str, 0);

		return;

	}

	while (dup != ddown + 1) {

		d = (dup - ddown)/2 + ddown;

		res = str_less(str, strs[d]);

		if (res == 0) {

			shift_array(str, d);

			return;

		}

		if (res > 0)

			ddown = d;

		else

			dup = d;

	}

	if (res > 0)

		shift_array(str, d+1);

	else

		shift_array(str, d);

}

int cmp(void* a1, void* a2) {

	return strcmp(*char**)a2*char**)a1;

}

int main(void) {

	int str_num = 0;

	char* str;

	int i = 0;

	while str = read_string != NULL) {

		strs[i++] = str;

		if (i == 1000)

			break;

	}

	qsort(strs, i, sizeof(char* cmp);

	if (i != 1000) {

		print_result(i);

		return 0;

	}

	while str = read_string != NULL) {

		insert_raw(str);

	}

	print_result(1000);

	return 0;

}

Работает так (с O3 в секундах).
test sort/tail моя
1 38 3
2 53 2
3 31 2.6
Вот так вот и проебывают ворк стейшены

Dasar

> Вообще, думаю, рулит самая тупая стратегия. Типа этой
есть еще два соображения:
1. массив из 1000 элементов можно держать частично отсортированным
2. не обязательно хранить только 1000 элементов в массиве - временами можно хранить и больше
оба соображения могут резко уменьшить кол-во сравнений, которые делаются при добавлении каждой строчки

procenkotanya

Какие-то странные у тебя времена. На моей машине (Celeron-M 1.3, 256 RAM):



          sort|tail -1000 <твоя прога>

test1.in   2.51              2.44

test2.in   4.60              1.21

test3.in   2.41              2.25

Как получается, что у тебя sort|tail так медленно работает?

Papazyan

Учитывая, что на моей машине прога работает без включенной оптимизации в 2-3 раза быстрее sort/tail, то это мы должны спросить тебя, что у тебя за sort/tail? Я не представляю как O(n logn) программа может работать наравне с O(n) программой.

Helga87

Я не представляю как O(n logn) программа может работать наравне с O(n) программой.

log(n) < 30, а константы у разных алгоритмов могут и в 100 раз различаться.

Papazyan

>>log(n) < 30, а константы у разных алгоритмов могут и в 100 раз различаться.
Я согласен. Поэтому и хочу узнать, что у него за sort/tail - интересно, что там за алгоритм.

procenkotanya

Мне что, бинарники послать? sort, tail - из debian etch от 2 сентября 2005
Время, если что, я меряю так:

 cat test$i.in | /usr/bin/time --format=%U $1 > s$i.out 2>time$i.out

И именно так его меряли на конкурсе в пятницу.
А как ты мерял?

Papazyan

Я немного не так, но и твой вариант у меня работает медленно. Какая версия пакета с sort у тебя? У меня textutils-2.0.21-5

procenkotanya

5.2.1-2

Papazyan

Под Debian он работает в 20 раз быстрее

procenkotanya

Есть предложение обменяться sort|tail.
Вот мои

Papazyan

Нет, твой sort (посмотри --version, у меня 2.0) такой же как у меня. Дело в Debian. Видимо у тебя (и у меня) все скомпилировано под конкретную машину. Но разница в 10 раз по сравнению с generic Red Hat - это п...ц.

procenkotanya

sort (coreutils) 5.2.1
Written by Mike Haertel and Paul Eggert.
Copyright (C) 2004 Free Software Foundation, Inc.
Это свободная программа; подробности об условиях распространения
смотрите в исходном тексте. Мы НЕ предоставляем гарантий; даже гарантий
КОММЕРЧЕСКОЙ ПРИГОДНОСТИ или ПРИГОДНОСТИ ДЛЯ КАКОЙ-ЛИБО ЦЕЛИ.

Olyalyau

Работает так (с O3 в секундах).
test sort/tail моя
1 38 3
2 53 2
3 31 2.6
Вот так вот и проебывают ворк стейшены

sort у тебя тормозит, скорее всего потому, что ты не передал ему LC_ALL=C в окружении, как
писал .
У меня:



$ time LC_ALL=C sort < /Cesspool/UpLoad/test1.in -T /Cesspool/UpLoad/ | tail -n 1000 > /dev/null

real    0m1.679s

user    0m1.100s

sys     0m0.239s



$ time sort < /Cesspool/UpLoad/test1.in -T /Cesspool/UpLoad/ | tail -n 1000 > /dev/null

real    0m28.897s

user    0m22.109s

sys     0m0.308s

А моя прога sort'у проигрывает на Sun'овских тестах, по очевидной (после заглядывания в тесты)
причине. Там даже профайлер не нужен, и так понятно, что значительная часть времени теряется
в operator < (string, string так как у строк длинные одинаковые префиксы. А RB-tree делает
больше сравнений, чем qsort.

Оставить комментарий