Тестовые задания в Яндексе. Часть 2.

Как и планировал, опробовал второй способ сортировки, а именно сортировку подсчетом. Кода в разы меньше, сам код куда проще, но… Крайне плохо масштабируемое решение с сильной зависимостью от количества доступной памяти. Так при использовании максимального количества доступной памяти в 256 Мб, приходится делать 64 прохода по файлу. Если же попытаться разнести чтение и запись (как я писал раньше, асинхронная запись дает ускорение приблизительно в 10-15%) то количество проходов вырастает до 128 и итоговая скорость оказывается даже меньше чем при последовательной обработке. Так же, мое решение не будет корректно работать в том случае, если количество одинаковых элементов превысит максимальное значение помещающееся в size_t.
Тем не менее, сортирует довольно быстро: 1 Гб, в среднем, обрабатывается за 108 секунд.

P.S. а вообще, я выдохся с данной задачкой (как делать ясно, побочные эффекты алгоритмов тоже очевидны), так что вернусь ней… через еще пару лет?

10 Comments Тестовые задания в Яндексе. Часть 2.

  1. Young

    Приветствую… Дай, угадаю – у тебя 32-х битная система? Ибо если sizeof(size_t) == 8 то вторая версия крашится.

    И если я ее верно пофиксил, то у меня получает она даже медленее чем первое решение – первое твое решение у меня за 4 минуты отрабатывает на 1gb, второе работает 10+ минут.

    У меня получилось решение которое у меня срабатывает за 1.5 минуты примерно – плюс его потенциальное еще можно на процентов 10-15 думаю ускорить.
    Все в рамках упрощенной задачи – в один поток, синхронно, без обработок ошибок

    Подсказать решение, или самому еще повозиться хочется?

    Кстати, мне мое самое быстрое решение сразу в голову пришло, но в процессе я также вспомнил о counting sort и отвлекся на него – но получилось медлено.

    Кстати, интересна следующая вещь – а не может ли быть пары решений, таких что одно будет быстрее на SSD, а другой будет быстрее на HDD.

    Я проверяю на SSD кстати, чуть поже проверю на HDD.

    Reply
    1. Alexander Stavonin

      Да, я не запускал вторую версию на 64 битах, а зря…
      Если говорить про первый случай, то думаю что в первом случае ты просто сливаешь все файлы одновременно. Так как при последовотельном слиянии у меня все работает где-то за 100 секунд (то что я писал про 3 минут фигня, т.к. все было собранно с отладочной информацией ).

      Reply
    2. Alexander Stavonin

      Кстати, ты свое решение куда-нибудь выложи, интересно же как другие сделали

      Reply
        1. Young

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

          Reply
    3. Alexander Stavonin

      Погонял твое решение. У меня оно отрабатывает за 41.347s против 35.38 в случае моего первого варианта (если замерять время через функцию time). Похоже что ты запускал отладочную версию моего решения, как и я в первый раз

      Reply
      1. Young

        Тут смотри что получается – у меня с оптимизациями (-O3) все равно твое первое решение получаетя медленее.

        70 секунд супротив 100 секунд, но при этом time говорит что у меня проц в моем варианте 30% загружен, в твоем 50%.

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

        Короче, задачу нужно уточнять

        Чуть поже нужно проверить на не мобильном i7+HHD – тогда твой вариат скорее будет быстрее.

        Ну или конечно нужно сделать микс моего – но это уже будет с потоками.

        Reply
        1. Alexander Stavonin

          Честно сказать, не очень понял почему твоя реализация работает
          Да, у тебя в run-скрипте запускается приложение сортировки без замера времени, как-то так: ./$EXEC_OUT $1, это нормально? У меня такое ощущение, что замеряется только лишь время на слияние файлов. :roll:

          Reply
          1. Young

            Уточни что не понял? Если сам алгоритм – это классический radix sort

            Я запускаю всегда time ./_run.sh – и измеряю время выполнения скрипта целиком. Так как время компиляции обычно меньше секунды, и удаление файлов старый не больше пару секунд – то просто забиваю на это и смотрю время выполнения скрипта целиком.

            Но в целом нужно добавить конечно – удаление файлов и конечное слияние в код.

Leave a Reply to Young Cancel reply