Сортировка 500000 строк длиной до 10 млн символов , Оптимальность алгоритма

[FasterHarder]

Всем программистам привет! Respect!
Помогите разобраться с алгоритмом (две реализации уже написал, но в обоих случаях не укладываюсь в отведенный лимит 1 секунды времени работы).
Условие: с клавиатуры вводится до 500000 строк (строка состоит ТОЛЬКО из латинских букв - большие и малые). Общая длина символов во всех строках не должна превышать 10 миллионов!! Нужно отсортировать строки в лексикографическом порядке по правилу: заглавная буква БОЛЬШЕ малой, если буквы одного регистра по та буква меньше, которая идет раньше по алфавиту (стандарт). Также: "Ivanov" < "Ivanova" (стандарт). Время ограничения работы программы 1 секунда!

реализовал через динамический массив + qsort получил что на 10000 строк и длиной в 7000 символов работает около 5 - 6 секунд, а ведь предельно допустимое значение могут быть в ТЫСЯЧИ раз больше!..Пробовал через ЛОС, тоже по лимиту не проходит серьезно...


подскажите оптимальный алгоритм для обработки сортировки таких строк....
подскажите как быть то??...буду очень признателен...

N.B. реализую на С, VS 2010, console application...

Сообщение отредактировано: FasterHarder - 22.11.10, 10:23

[Grab[SSAU]]

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

[FasterHarder]

Цитата Grab[SSAU] @ 22.11.10, 10:22

строить бинарное дерево. Таким образом, решением будет трасса его обхода Лево-Центр-Право.

именно двоичное (бинарное) дерево (не avl)? Корень дерева будет ПЕРВАЯ введенная строка??...

Добавлено 22.11.10, 10:27
еще хочется до конца понять что в подобных задачах считается временем работы программы!...т к ввод с клавиатуры может занимать +бесконечность времени, вывод на экран отсортированных строк - безумно долгая операция, поэтому может длиться недели по сути...
кстати, обход (просто обход без печати даже) разве уложиться в 1 секунду?...

Добавлено 22.11.10, 10:29
т е обход бинарного дерева (прыгая чисто указателями) из 500 000 узлов пройдет за 1 секунду?...если нет, тогда вообще непонятно, что считать за 1 секунду работы...

[Grab[SSAU]]

FasterHarder, секундочку, я не успеваю читать

Цитата FasterHarder @ 22.11.10, 10:25

именно двоичное (бинарное) дерево (не avl)? Корень дерева будет ПЕРВАЯ введенная строка??...

Да, бинарная. Предлагаю начать с него, потому что оно попроще АВЛ или красно-чёрного. Да, корнем будет первая введённая строка.

Цитата FasterHarder @ 22.11.10, 10:25

еще хочется до конца понять что в подобных задачах считается временем работы программы!...т к ввод с клавиатуры может занимать +бесконечность времени, вывод на экран отсортированных строк - безумно долгая операция, поэтому может длиться недели по сути...
кстати, обход (просто обход без печати даже) разве уложиться в 1 секунду?...

Вас проверяет автоматизированная система. "Ввод с клавиатуры" там максимально быстр, равно как и "вывод на экран". Как она замеряет время мне неведомо, но подозреваю, что по-честному

Уложится ли обход в секунду не знаю, предполагаю, что да. Ведь это всего лишь рекурсия с глубиной не более log2(500 000) < 19 вызовов.

[FasterHarder]

Цитата Grab[SSAU] @ 22.11.10, 10:40

Уложится ли обход в секунду не знаю, предполагаю, что да. Ведь это всего лишь рекурсия с глубиной не более log2(500 000) < 19 вызовов.

при некоторых входных данных (каждое слово меньше предыдущего) би-дерево вырождается в список!..., т е будет рекурсия в 500 000 - 1 вложенности, правда на сколько это на скорость повлияет не знаю...
в общем я тоже думал про деревья, но думал что через списки 100% отработает...

в общем нужно проверить...

[Grab[SSAU]]

Цитата FasterHarder @ 22.11.10, 10:46

при некоторых входных данных (каждое слово меньше предыдущего) би-дерево вырождается в список!..., т е будет рекурсия в 500 000 - 1 вложенности,

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

[FasterHarder]

в общем реализовал следующее: поскольку не важно ЧТО хранится в узлах дерева, составил би-дерево из целых чисел. Ведь важна скорость ОБХОДА дерева а информационное поле не влияет на скорость обхода!...
заполнял случайными числами от -100 до +100, заполнялось минуты 3, а скорость обхода показала 0 секунд (что радует безусловно)...НО когда стал тестировать граничный вариант (заполнял только фиксированное информационное поле = 1), то программа вылетает при количестве узлов 4700, а при 4699 работает корректно, следовательно максимальное количество вложенности рекурсии 4699???....

понятно почему при 50000 узлов отработало корректно, потому что числа были равномерно распределены на диапазоне от -100 до 100 и дерево "росло" одинаково по всем направлениям....

можно как-нибудь обойти проблему с добавлением одинаковых узлов???

N.B. Реализация алгоритма через би-дерево:

#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
typedef struct Telem
{
    int inf;
    struct Telem *left;
    struct Telem *rigth;
} Telem;
// добавление узла в дерево (если значение РАВНО узел "уходит" в правую часть)
Telem * addNode(Telem *proot, int pinf)
{
    if(!proot)
    {
        proot = (Telem *)malloc(sizeof(Telem));
        if(!proot)
        {
            printf("\n\nError memory!");
            getch();
            exit(1);
        }
        proot->inf = pinf;
        proot->left = proot->rigth = NULL;
    }
    else
    {
        if(proot->inf > pinf)
            proot->left = addNode(proot->left, pinf);
        else
            proot->rigth = addNode(proot->rigth, pinf);
    }
    return proot;
}
// обход дерева слева направо: левый узел - корень - правый узел
void lkr(Telem * proot)
{
    if(proot)
    {
        lkr(proot->left);
        //printf("%d ", proot->inf);
        lkr(proot->rigth);
    }
}
// удаление дерева из памяти
Telem* delTree(Telem *p)
{
    if(p)
    {
        if(p->left != NULL)
            p->left = delTree(p->left);
        if(p->rigth != NULL)
            p->rigth = delTree(p->rigth);
        free(p);
    }
    return NULL;
}
int main()
{
    Telem *root = NULL;
    long i, n, x;
    int start, end;
    printf("Vvedite kolichestvo elementov: ");
    scanf("%d", &n);
    printf("\n\nVhodnie znacheniya: ");
    for(i = 0; i < n; i++)
    {
        x = 1;          // rand() % 201 - 100;          // [-100 ... 100]
        //printf("%d ", x);
        root = addNode(root, x);
    }
    
    printf("\n\nDerevo imeet vid: ");
    // засекаем время исключительно обхода без печати
    start = time(NULL);
    lkr(root);
    end = time(NULL);
    printf("\n\nVremya obhoda (sek): %d", (end - start));
    getch();
 
    delTree(root);
    return 0;
}

Сообщение отредактировано: FasterHarder - 22.11.10, 11:38

[Grab[SSAU]]

FasterHarder, я ошибся с деревом, забыв про граничные случаи А этой задачи в открытом доступе нет? Самому интересно стало

[FasterHarder]

Цитата Grab[SSAU] @ 22.11.10, 11:53

А этой задачи в открытом доступе нет?

у меня на бумажке написана...наверное в public-доступе нет...
я вроде условие четко сформулировал, все ясно...если что непонятно могу конечно пояснить...

N.B. может hash - таблицу ввести, а ключом будет первая буква, правда опять таки при идентичных строках вырождается в ЛОС...-> full scan...

Добавлено 22.11.10, 12:03
еще очень хочется понять следующее: если имеется набор таких НЕ отсортированных строк в количестве 500 000 штук, то даже теоретически НЕ успеть их отсортировать за 1 - 2 секунды любым существующим способом сортировки?? если да, тогда однозначно нужно сортировать при вводе сразу и в этом случае скорость будет зависит ТОЛЬКО от просмотра всех элементов структуры данных....

вообще, простой цикл от 1 до 500 000 работает точно быстрее 1 сек....

[ss]

А где это будет выполняться?
У меня стабильно выдаёт 800+-50:

#include "stdafx.h"
#include <vector>
#include <algorithm>
#include <stdlib.h>
#include <iostream>
#include <time.h>
 
 
struct lpstr_less
{
    bool operator ()(const TCHAR *_left, const TCHAR *_right)
    {
        return (_tcscmp( _left, _right ) < 0);
    }
};
 
void main()
{
    std::vector<TCHAR*> v(500000);
 
    std::vector<TCHAR*>::iterator i = v.begin();
    for ( ; i != v.end(); i++ )
    {
        *i = new TCHAR[28];
        _stprintf_s( *i, 28, _T("%d%d%d"), rand()*rand(), rand()*rand(), rand());
    }
 
    long c;
    c = clock();
    std::sort( v.begin(), v.end(), lpstr_less() );
    std::cout << clock() - c;
 
    getchar();
}

Естественно, std::sort придётся заменить на свою реализацию quicksort'а. Но факт: на некоторых машинах (на моей, например) вполне себе без дерева обходимся.

Добавлено 22.11.10, 12:21
Вообще, это сильно зависит от контекста задачи: она на умение писать на чистом C быстрые алгоритмы, или на знание структур данных, или на знание STL, или ещё чего?..

[FasterHarder]

я понял почему так долго работал мой вариант, еще через qsort, потому что тестировал на строках до 10 млн, а ведь по условию ОБЩАЯ длина всех строк не превышает 10 млн, т е если 500 000 строк, то их МАКС. длина = 20!...в этом случае программа работает 2 секунды...нужно малость оптимизировать сортировку, а особенно "сравнение символов"...

Добавлено 22.11.10, 12:24

Цитата ss @ 22.11.10, 12:09

или на знание STL

ну это явно НЕ для СИ!...
а задача совокупно на все...в этой задачи простые структуры данных, поэтому основное - написать оптимальный вариант сравнения строк при сортировке...

Сообщение отредактировано: FasterHarder - 22.11.10, 12:26

[ss]

int __cdecl strcmp (
        const char * src,
        const char * dst
        )
{
        int ret = 0 ;
 
        while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst)
                ++src, ++dst;
 
        if ( ret < 0 )
                ret = -1 ;
        else if ( ret > 0 )
                ret = 1 ;
 
        return( ret );
}

[FasterHarder]

у меня нечто подобное:

int compstr(char *ps1, char *ps2)
{
    for( ; *ps1 == *ps2; ++ps1, ++ps2 )
        if( *ps1 == 0 )
        return 0;
    if(*ps1 >= 'a' && *ps2 <= 'Z')  // ps2 > ps1
        return 1;
    if(*ps1 <= 'Z' && *ps2 >= 'a')  // *ps1 > *ps2
        return -1;
    return  *ps1 < *ps2 ? 1 : -1;
}

[MBo]

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

[Bug Hunter]

Цитата FasterHarder @ 22.11.10, 12:00

если имеется набор таких НЕ отсортированных строк в количестве 500 000 штук, то даже теоретически НЕ успеть их отсортировать за 1 - 2 секунды любым существующим способом сортировки??

Совершенно верно - отсортировать такой объем данных невозможно в принципе. Но решить задачу можно! Как? Да не сортировать ничего, надо завести суффиксное дерево (в правильности термина не уверен), пихать в него то, что вводится, а потом тупо вывести то, что в него окажется запихнутым в лексигрофическом порядке. Вычислительная стоимость такого решения будет порядка стоимости ввода-вывода из файла/в файл.

Цитата FasterHarder @ 22.11.10, 10:25

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

Гонзалес, ты что, никогда не слышал про переназначение стандартных входных/выходных потоков консольных приложений на файлы? Открой любой букварь, там это где-то в начале есть. Да, собственно, на Тимусе объяснено, как организовать программу, чтобы отлаживать ее у себя на компе, со своими данными, и отправлять на проверку без внесения изменений.

[leo]

Цитата FasterHarder @ 22.11.10, 12:00

еще очень хочется понять следующее: если имеется набор таких НЕ отсортированных строк в количестве 500 000 штук, то даже теоретически НЕ успеть их отсортировать за 1 - 2 секунды любым существующим способом сортировки?? если да, тогда однозначно нужно сортировать при вводе сразу и в этом случае скорость будет зависит ТОЛЬКО от просмотра всех элементов структуры данных....

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

Цитата FasterHarder @ 22.11.10, 12:23

в этой задачи простые структуры данных, поэтому основное - написать оптимальный вариант сравнения строк при сортировке...

Условие слишком мудреное, поэтому существенно\кардинально ускорить сравнение непосредственно самих строк вряд ли получится. Явное ускорение может дать пред\пост-обработка, например, замена регистра символов в самих строках, либо еще лучше использование хэшей, учитывающих эту замену. Например, можно прогнать расчет и быструю предсортировку по 4 или 8 байтному хэшу, а затем итоговую постсортировку участков с совпадающими хэшами (типа прямых вставок).
PS: Ес-но подразумевается, что хэш расчитывается один раз и сохраняется в "простой структуре данных" в месте с указателем на строку. При этом достигается существенное ускорение как за счет упрощения сравнений на каждом шаге, так и за счет улучшения условий кэширования данных в процессоре (поскольку при сортировке обращение происходит только к массиву структур, а не к куче строк в 10 млн.символов)

Сообщение отредактировано: leo - 22.11.10, 17:02

[FasterHarder]

Цитата leo @ 22.11.10, 16:59

наталкивает на мысль, что скорее всего это подвох и сортировать\упорядочивать строки можно\нужно именно в процессе их ввода

безусловно, подобные мысли возникали!...Тогда логически появляется следующая диллема: должна ли ТОЛЬКО что введенная строка УСПЕВАТЬ позиционироваться в нужную позиции динамической структуры или нет за ОДНУ секунду...если НЕТ, тогда получается, что в такой программе НЕ будет фрагмента куда ПОТРАТИТЬСЯ отведенная секунда...если да, то даже full scan по ЛОС со всеми проверками должен успеть отработать за 1 сек. (у меня кстати, такая реализация есть, она не прошла ПО ЛИМИТУ в одну секунду)....

P.S.

Цитата leo @ 22.11.10, 16:59

замена регистра символов в самих строках,

, но ведь это приведет к их модификации и тогда каков в этом смысл...непонятно...

N.B. существующая программа работает около 2 секунд (миллисекунды не засекал)...

Цитата FasterHarder @ 22.11.10, 11:37

максимальное количество вложенности рекурсии 4699???....

[leo]

Цитата FasterHarder @ 22.11.10, 18:25

но ведь это приведет к их модификации и тогда каков в этом смысл...непонятно...

Смысл в том, что эта модификация обратимая и производится всего 2 раза (1 до и 1 после сортировки), т.е. имеет сложность 2*N, что несущественно по сравнению со сложностью самой сортировки N*log(N) ~ 19*N при N=500тыс. Однако такая модификация должна упростить\ускорить каждое сравнение (особенно на современных камнях, тормозящих на хаотических условных переходах), и в итоге общая скорость может быть выше, чем при непосредственных хитроумных сравнениях

[FasterHarder]

Цитата leo @ 22.11.10, 18:46

производится всего 2 раза (1 до и 1 после сортировки)

я в общем не понимаю смысл такой пре / пост обработки...например, есть 4 слова:
1) hello
2) heLlo of
3) Hello o
4) hellO of

что будет происходить с каждой строкой по вашей задумке??...

[Bug Hunter]

Цитата leo @ 22.11.10, 16:59

1) именно о вводе с клавиатуры (несмотря на явно нереальное число строк для ручного ввода)

leo, ты то чего тормозишь? Совершенно понятно, что ввод с клавиатуры - это отсебятина "переводчика", имеется в виду ввод со стандартного входного потока. Собственно запуск на тестирование будет осуществляться так:

myprog.exe <data.in >data.out

ну, естественно, из тестирующей программы через exec(...).

Цитата leo @ 22.11.10, 16:59

2) об абсолютном времени в 1 сек безотносительно к компу

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

Цитата leo @ 22.11.10, 16:59

Явное ускорение может дать пред\пост-обработка, например, замена регистра символов в самих строках,

Ни понял - сортировку по условию надо с учетом регистра осуществлять

Добавлено позже: Тьфу ты блин, старость не радость, дошло.

Сообщение отредактировано: Bug Hunter - 23.11.10, 08:49

[MBo]

Короче, проверил на компе 4-летней давности Athlon 3500+ (2.2 ГГц).
500 000 строк длиной от 15 до 20 символов.

Предобработка и постобработка - просто XOR символов с $60 (0x60)

Предобработка + обыкновенный Quicksort + постобработка ~ 800-850 мс
Предобработка + RadixSort MSD c обработкой малых кусков вставками, оптимизацией не занимался + постобработка - те же яйца

[leo]

Цитата FasterHarder @ 22.11.10, 18:58

что будет происходить с каждой строкой по вашей задумке??...

Инверсия регистра, т.е. малые буквы станут прописными и наоборот - как при наборе текста при нажатой Caps Lock, например, "Hello" -> "hELLO".

Цитата MBo @ 23.11.10, 05:14

Предобработка и постобработка - просто XOR символов с $60 (0x60)

Почему 0x60, а не 0x20 ? А если строка содержит пробелы и знаки препинания ?
В стандартных ASCII и Unicode кодировках малые и прописные латинские буквы различаются на 'a'-'A' = 'a'^'A' = 32 = 0x20, поэтому инверсию регистра можно делать операцией s[i] ^= 0x20. Разумеется, если строка кроме букв может содержать пробелы и знаки препинания, то инверсию нужно делать только для букв.

[FasterHarder]

Цитата leo @ 23.11.10, 07:27

Инверсия регистра, т.е. малые буквы станут прописными и наоборот - как при наборе текста при нажатой Caps Lock, например, "Hello" -> "hELLO".

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

Цитата leo @ 23.11.10, 07:27

А если строка содержит пробелы и знаки препинания ?

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

Цитата MBo @ 23.11.10, 05:14

Предобработка + обыкновенный Quicksort + постобработка

опять таки, какой выйгрыш дает пред / пост обработка?...

[Bug Hunter]

Цитата MBo @ 23.11.10, 05:14

Короче, проверил на компе 4-летней давности Athlon 3500+ (2.2 ГГц).
500 000 строк длиной от 15 до 20 символов.

Предобработка и постобработка - просто XOR символов с $60 (0x60)

Предобработка + обыкновенный Quicksort + постобработка ~ 800-850 мс

Т.е. получается, что задача тупо на инвертирование? Мдя, на всякого мудреца довольно простоты ©.

[leo]

Цитата FasterHarder @ 23.11.10, 08:40

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

Для того, чтобы при сортировке использовать более простую и соотв-но более быструю функцию сравнения типа strcmp вместо твоей "навороченной" compstr из #13 с кучей условий.
PS: Инверсия регистра как раз удовлетворяет условию сравнения #1, т.к. 1) заглавные и малые меняются местами, 2) соотношение между буквами одного регистра не изменяется, т.к. сохраняется их алфавитный порядок

Добавлено 23.11.10, 09:09

Цитата Bug Hunter @ 23.11.10, 08:56

Т.е. получается, что задача тупо на инвертирование?

Если вместо инверсии самих строк использовать int хэш (те же 4 первых символа строки с инверсией регистра и порядка следования), то должно быть еще раза в 1.5-2 быстрее (если конечно не брать тупой случай, когда у всех строк первые 4 символа одинаковые)

Сообщение отредактировано: leo - 23.11.10, 09:09

[FasterHarder]

leo, все, теперь понял, пасибо...проверю как это повысит производительность, правда буду использовать не 0X60, а функции поднимающие в верхний / нижний регистр...

Добавлено 23.11.10, 09:16

Цитата leo @ 23.11.10, 09:03

если конечно не брать тупой случай, когда у всех строк первые 4 символа одинаковые

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

[Bug Hunter]

Цитата leo @ 23.11.10, 09:03

чтобы при сортировке использовать более простую и соотв-но более быструю функцию сравнения типа strcmp вместо твоей "навороченной" compstr из #13 с кучей условий.

А можно оптимизировать compstr как-то так:

int compstr(char *ps1, char *ps2)
{
   for( ; *ps1 == *ps2; ++ps1, ++ps2 )
       if( *ps1 == 0 ) return 0;
   return  ((*ps1)^0x20) < ((*ps2)^0x20) ? -1 : 1;
}

- тогда предобработка+постобработка не понадобятся.

Сообщение отредактировано: Bug Hunter - 23.11.10, 10:49

[Bug Hunter]

Цитата leo @ 23.11.10, 09:03

Если вместо инверсии самих строк использовать int хэш (те же 4 первых символа строки с инверсией регистра и порядка следования), то должно быть еще раза в 1.5-2 быстрее (если конечно не брать тупой случай, когда у всех строк первые 4 символа одинаковые)

При равномерном распределении большинство строк (51/52) будут различаться по первому символу и подавляющее большинство (99.963%) - по первому или второму, так что дополнительные изыски тут в среднем вряд ли помогут, а вот в этом предельном плохом случае:

Цитата FasterHarder @ 23.11.10, 09:10

скорость работы также тестируется на варианте, когда максимальное количество строк и все строки равны, т е НЕ только первые 4 символа, а абсолютно все...

дополнительные действия будут явно мешать.

Кста, в этом предельном случае стандартный qsort должен тупо вывалиться по переполнению стэка! Возможно, задача еще и на это...

[FasterHarder]

Цитата Bug Hunter @ 23.11.10, 09:50

вывалиться по переполнению стэка!

да, так и есть на самом деле!...

Добавлено 23.11.10, 10:29
да, и еще, поскольку сортировка ПОСЛЕ ввода на граничных случаях НЕ проходит, то наталкивает на мысль, что сортировать нужно СРАЗУ при вводе!...
вижу только такой вариант: ввели строку, бинарным поиском определили позицию вставки, после этого сместили строки вправо на одну позицию (правда, насколько тяжелая операция может быть), в освобожденное место вставили вводимую строку...

конечно, бинарный поиск будет работать почти мгновенно: 2^x >= 500 000 (уже говорили, что 19 вроде), а вот сдвиг...максимальный сдвиг будет в том случае, когда добавляется ПОСЛЕДНЯЯ строка и она попадает в первую позицию, в этом случае 499 999 строк, смещаются вправо на одну позицию..если эта операция отработает быстрее 1 сек. то задача думаю будет решена точно...

[Bug Hunter]

Цитата Bug Hunter @ 23.11.10, 09:42

можно оптимизировать compstr как-то так:

Sorry, напортачил, не послушавшись совета от leo (использовать xor 0x20, а не 0x60), исправил, смотрите исправленный вариант (#27).

[Bug Hunter]

Цитата FasterHarder @ 23.11.10, 09:51

да, так и есть на самом деле!...

да, и еще, поскольку сортировка ПОСЛЕ ввода на граничных случаях НЕ проходит, то наталкивает на мысль, что сортировать нужно СРАЗУ при вводе!...
вижу только такой вариант: ввели строку, бинарным поиском определили позицию вставки, после этого сместили строки вправо на одну позицию (правда, насколько тяжелая операция может быть), в освобожденное место вставили вводимую строку...

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

Но если хочется помучиться...

Цитата FasterHarder @ 23.11.10, 09:51

конечно, бинарный поиск будет работать почти мгновенно: 2^x >= 500 000 (уже говорили, что 19 вроде), а вот сдвиг...

Можно заполнять массив указателей с хвоста и сдвигать элементы вреред - тогда можно воспользоваться memcpy или как его там - это должно быть быстро. Было бы любопытно сравнить с qsort.

[leo]

Цитата Bug Hunter @ 23.11.10, 09:50

При равномерном распределении большинство строк (51/52) будут различаться по первому символу и подавляющее большинство (99.963%) - по первому или второму, так что дополнительные изыски тут в среднем вряд ли помогут

Еще как помогут, и в #18 я уже объяснил почему. Сделав один единственный проход по массиву для вычисления int-хэша (что кстати можно сделать и одновременно со считыванием строк) затем при сортировке все сравнение сводится к элементарной inline-операции сравнения двух int. А твоя compstr из #27, даже если и заинлайнится, то потребует кучу непроизводительных операций по сохранению, инициализации и восстановлению регистров, не говоря уже об условных переходах, а если не заинлайнится, то плюс нехилые затраты на вызов и возврат из функции. И все это прямые потери на каждом из ~N*log(N) сравнений (в лучшем случае).
Плюс к этому значительно (если не сказать кардинально) улучшаются условия кэширования данных в процессоре, т.к. int-хэш сохраняется в одной 8-байтовой структуре вместе с указателем на строку и соотв-но фактически сортируется сам массив, содержащий эти хэши (без обращения к отдельно лежащим строкам). Во-первых, этот массив по размеру в 2-3 раза меньше чем сами строки, во-вторых, что более существенно, за счет сортировки самого массива на каждой итерации qsort'а идет последовательное обращение только к двум участкам памяти (концам текущего диапазона сортировки) и при этом современные процессоры прекрасно справляются с предсказанием и упреждающей подгрузкой данных из ОЗУ в кэш (hardware prefetch). А если сравнивать не хэши, а отдельно лежащие строки, то только на первой итерации доступ к этим строкам может быть квазипоследовательным, а на последующих итерациях он все более становится случайным (ес-но предполагаентся, что сортируется массив указателей, а сами строки остаются на своих местах). А в современных компах случайный доступ к ОЗУ на один-два порядка (!) медленнее последовательного - вот и считай "вряд ли помогут" или нет.
Ну, а что касается пост-сортировки, то исходя из твоих же предположений о различиях строк, простейшая повторная сортировка вставками должна отработать за O(N), что также значительно быстрее сортировки "в лоб"

Сообщение отредактировано: leo - 23.11.10, 12:59

[Bug Hunter]

Цитата leo @ 23.11.10, 12:52

Еще как помогут, и в #18 я уже объяснил почему.

У тебя там небольшая неточность - имперически установлено, что кол-во сравнений в быстрой сортировке для хорошо перемешанных данных сост. ~2NLnN, т.е. 26N для 500 000, т.е. 26 сравнений на строку. Да, заморочится с int-кэш явно стоит, причем ввиду того, что большинство строк расходится по первым символам, доколачивать прикладом после сортировки хэшей всего ничего останется. Все, полностью понял твою мысль.