Что посоветуете делать? Алгоритмы(+)

[Mike_MIPT]

Вот в очередной раз на работе встала задача повышения скорости работы серверного кода. Требовалось проводить сортировку порядка 10^5-10^6 строк за время меньше 1сек. Стандартный код на С++ сделал сортировку 10^5 строк за 2 сек. После некоторой оптимизации сортировка на тех же данных заняла 0.6 сек., что и пошло в проект. Но мне этого показалось мало, и в результате, подумав пару выходных, был выдан код который сортирует данные еще в 10 раз быстрее( за время ~сумме длин строк ). Вот сижу и думаю, как разминка для ума это хорошо, но может надо все запатентовать и продать тому же ораклу или еще кому. Вообще как считаете, такие алгоритмы и вообще специалисты-алгоритмисты кому нибудь нужны или нет? Что скажите?

[Dmitry67]

Если Вы придумали алгоритм который сортирует за время лучше чем N*ln(N)
то Вам бы светила бы нобелевка... если бы их давали по математике

[tengiz]

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

Хорошие алгоритмы разумеется нужны и всегда приветствуются. А разминать ум это всегда хорошо, даже если потом окажется, что придумываешь что-то что давно известно. Что касается патентования - убедитесь, что Вы не изобретаете велосипед - судя по объёмам Вам не нужна внешняя память и, возможно, Вам необязательно сортировать "на месте".

[tengiz]

Если Вы придумали алгоритм который сортирует за время лучше чем N*ln(N) то Вам бы светила бы нобелевка...

Увы, за radix sort, который работает быстрее, чем N*ln(N), никому ничего не дали. Да и непонятно на самом деле кому давать - чернорабочим от бумажного делопроизводства вариации этого алгоритма были известны давным давно.

[Mike_MIPT]

Вообще то работает именно за линейное время. И в 10-20 раз быстрее альтернатив. Вообще алгоритмы сортировки за линейное время известны давно. Всякие сортировки подсчетом и прочие. У них свои ограничения на типы сортируемых объектов. С другой стороны разрешающие деревья никто не отменял, и потому при использовании простых сравнений время n*ln(n). Вопрос в другом, я уверен, что изобрел велосипед. Даже допускаю, что велосипед уже и запатентован. Вопрос в другом, я знаю об этом велосипеде или могу его придумать. Я встречал мало людей, которые это могут сделать. Считайте это моим хобби. Причем постоянно попадаются подобные задачи и очень часто я понимаю, что не встречал ни одной системы с правильным решением. Так вот интересно, надо ли это кому нибудь или нет? Или действительно надо патентовать велосипед, пока другие не запатентовали? Или продаться кому, только кому?

[hooch]

Вообще то работает именно за линейное время. И в 10-20 раз быстрее альтернатив. Вообще алгоритмы сортировки за линейное время известны давно. Всякие сортировки подсчетом и прочие. У них свои ограничения на типы сортируемых объектов. С другой стороны разрешающие деревья никто не отменял, и потому при использовании простых сравнений время n*ln(n). Вопрос в другом, я уверен, что изобрел велосипед. Даже допускаю, что велосипед уже и запатентован. Вопрос в другом, я знаю об этом велосипеде или могу его придумать. Я встречал мало людей, которые это могут сделать. Считайте это моим хобби. Причем постоянно попадаются подобные задачи и очень часто я понимаю, что не встречал ни одной системы с правильным решением. Так вот интересно, надо ли это кому нибудь или нет? Или действительно надо патентовать велосипед, пока другие не запатентовали? Или продаться кому, только кому?

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

[Melkor]

Если Вы придумали алгоритм который сортирует за время лучше чем N*ln(N) то Вам бы светила бы нобелевка...

Увы, за radix sort, который работает быстрее, чем N*ln(N), никому ничего не дали. Да и непонятно на самом деле кому давать - чернорабочим от бумажного делопроизводства вариации этого алгоритма были известны давным давно.

Так radix sort в данном случае как раз и будет иметь сложность, пропорциональную сумме длин строк. Может, это он и есть?

[Mike_MIPT]

Так radix sort в данном случае как раз и будет иметь сложность, пропорциональную сумме длин строк. Может, это он и есть?

Не совсем так. Насколько я понимаю, radix sort для плохих сток такого времени не даст, например если одна строка в миллион символов и миллион строк по 1 символу. С какого разряда начать? Ну да суть не в этом, уверен, что добрая половина читающих немного подумав написала бы 40 строчек для решения задачи. Вопрос в другом, может это никому не нужно? Почему серваки сортируют 100 000 строчек секунды? Люди пользуют qsort в местах, где реально могут придти плохие данные и время станет ужасным уже на 10 000 объектах?
Сортировка это частный пример, вопрос в том, нужно ли это кому, и если да, кому? А насчет патентования, я иногда встречаю задачи, на которые находятся решения лучшие или сильно лучшие, чем те, что я где либо встречал. Так наверняка что-то из этого можно запатентовать и продать тому же ораклу/циске/еще кому?

[Melkor]

Так radix sort в данном случае как раз и будет иметь сложность, пропорциональную сумме длин строк. Может, это он и есть?

Не совсем так. Насколько я понимаю, radix sort для плохих сток такого времени не даст, например если одна строка в миллион символов и миллион строк по 1 символу. С какого разряда начать?

Ну, первым шагом можно составить таблицу длин и использовать длину строки в качестве первого разряда для сортировки, далее начинать с последнего символа и двигаться по этой таблице длин. Конечно, в совсем плохих случаях (строка длиной в миллион символов) составление этой таблицы потребует немного дополнительных усилий.

Почему серваки сортируют 100 000 строчек секунды? Люди пользуют qsort в местах, где реально могут придти плохие данные и время станет ужасным уже на 10 000 объектах?
Сортировка это частный пример, вопрос в том, нужно ли это кому, и если да, кому? А насчет патентования, я иногда встречаю задачи, на которые находятся решения лучшие или сильно лучшие, чем те, что я где либо встречал. Так наверняка что-то из этого можно запатентовать и продать тому же ораклу/циске/еще кому?

Думаю, в тех случаях, когда скорость действительно критична (в симуляциях, например), быстрые алгоритмы окажутся востребованными.

[Okie]

В games programming алгоритмы тоже вещь полезная. Везде, где нужно real-time rendering или чего-то там еще real-time

[Mike_MIPT]

Ну, первым шагом можно составить таблицу длин и использовать длину строки в качестве первого разряда для сортировки, далее начинать с последнего символа и двигаться по этой таблице длин. Конечно, в совсем плохих случаях (строка длиной в миллион символов) составление этой таблицы потребует немного дополнительных усилий.

Все логично, я тоже примерно так и начал. И основа та же, отказаться от сравнений строк целиком. Есть свои тонкости. Глвное что результат получился и это радует. Огорчает, почему я подобного результата в работающих системах не видел. Может я чего-то недопонимаю?

Думаю, в тех случаях, когда скорость действительно критична (в симуляциях, например), быстрые алгоритмы окажутся востребованными.

Я то же подумывал. Правда на серьезные фирмы выхода нет, а тем кто на готовых движках текстуры лепит это не надо. Да и задача вроде в приложении к сервакам появилась.
Еще была мысль всякий околонаучный софт писать, но поговорив с людьми, которые для спутников софт пишут понял, почему спутники до марса долетают, а отозваться уже не могут. (Это ж надо таких деятелей набрать, писать софт для оборудования в сотни мегабаксов ). Кстати, а москве кто пишет движки для игрушек?