Автор Тема: Задачка на сортировку файла  (Прочитано 20902 раз)

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Задачка на сортировку файла
« Ответ #60 : Декабрь 03, 2012, 09:09:44 pm »
Странно. А почему так? Есть соображения?

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Задачка на сортировку файла
« Ответ #61 : Декабрь 03, 2012, 09:29:30 pm »
Добрался до винды (замечу, это другая машина - в два-три раза примерно более шустрая чем линуксячья).

Значит так. Во-первых размер бинаря у меня 180 Кб где-то. Это собранное mingw.
Во-вторых там ввод таки тормоз - полторы секунды на девятимегабайтном файле.

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

Результаты (изначальный файл - 9 Мб):
Lua:
ETime(   0:00:00.982 ) UTime(   0:00:00.873 ) KTime(   0:00:00.093 )
ITime(   0:00:00.000 )

C++:
ETime(   0:00:00.700 ) UTime(   0:00:00.624 ) KTime(   0:00:00.062 )
ITime(   0:00:00.000 )

Делаем выводы:
1) в стандартной гнутой (GNU) плюсовой либе getline сделан отвратительно с точки зрения скорости. Особенно под виндой - там оно тормозит так, что аж медленная lua начинает обгонять.
2) Со вводом в мелкомягкой плюсатой либе в этом месте все хорошо.
3) Неоптимальный плюсатый алгоритм (с постоянными сортировками) работает примерно в два раза быстрее чем более оптимальный на Lua (несмотря на то, что сортировка в Lua делается сишным кодом).
4) Студия пока стандарту не научилась.
Y = λf.(λx.f (x x)) (λx.f (x x))

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Задачка на сортировку файла
« Ответ #62 : Декабрь 03, 2012, 09:49:47 pm »
Нашел :-)
Добавил одну ма-аленькую строчку кода и в линуксе стало так (начальный алгоритм):
c++
$ time ./a.out < conf.txt > /dev/null

real    0m0.890s
user    0m0.820s
sys     0m0.072s
lua:
$ time lua ilovb.lua < conf.txt~ > /dev/null

real    0m4.127s
user    0m4.052s
sys     0m0.072s
Y = λf.(λx.f (x x)) (λx.f (x x))

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Задачка на сортировку файла
« Ответ #63 : Декабрь 03, 2012, 10:26:24 pm »
А вот что подвендой (подвинда у меня на более новом ноуте (куплен буквально пару-тройку недель назад), там модный i5 с этим, как его, Ivy Bridge, а линукс на старом ноуте которому уже 4 года - там просто мобильная версия Core2 Duo).

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

С++ без магической строчки (mingw):
ETime(   0:00:10.686 ) UTime(   0:00:09.843 ) KTime(   0:00:00.842 )
ITime(   0:00:00.000 )
Lua:
ETime(   0:00:02.917 ) UTime(   0:00:02.667 ) KTime(   0:00:00.249 )
ITime(   0:00:00.000 )
С++ c магической строчкой (mingw):
ETime(   0:00:03.369 ) UTime(   0:00:02.152 ) KTime(   0:00:01.216 )
ITime(   0:00:00.000 )
С++ msvc:
ETime(   0:00:01.934 ) UTime(   0:00:01.809 ) KTime(   0:00:00.124 )
ITime(   0:00:00.000 )
Y = λf.(λx.f (x x)) (λx.f (x x))

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Задачка на сортировку файла
« Ответ #64 : Декабрь 03, 2012, 10:27:01 pm »
Ах, да. Магическая строчка:
ios::sync_with_stdio(false);
Y = λf.(λx.f (x x)) (λx.f (x x))

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Задачка на сортировку файла
« Ответ #65 : Декабрь 03, 2012, 10:31:16 pm »
Да, на старом ноуте все 32битное, на новом - 64х.
Y = λf.(λx.f (x x)) (λx.f (x x))

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Задачка на сортировку файла
« Ответ #66 : Декабрь 04, 2012, 05:29:50 am »
Вот теперь похоже на cpp  :D

ps Прикрепил содержимое моего монструозного бинаря. Может так прояснится

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Задачка на сортировку файла
« Ответ #67 : Декабрь 04, 2012, 07:50:36 am »
Поправил еще одну ошибку и сделал чтобы убирались лишние отступы
function print_tree(tree, indent)
    indent = indent or 0
    for _, branch in ipairs(tree.children) do
        print(string.rep('\t', indent) .. branch.value)
        if branch.children then
            print_tree(branch, indent + 1)
        end
    end
end

function comp(a, b)
    return a.value < b.value
end

function read(file)
    local line = file:read()
    if not line then
        print('error 002')
        return nil
    end
    local _, indent = line:find('^\t+')
    indent = indent or 0
    local last = indent
    local first = indent
    local tree = {children = {}}
    local branch
    while line do
        _, indent = line:find('^\t+')
        if indent < first then
            print('error 001')
            return nil
        end
        if indent > last then
            tree = branch
            tree.children = {}
            last = last + 1
        else
            while indent < last do
                table.sort(tree.children, comp)
                tree = tree.parent
                last = last - 1
            end
        end
        branch = {parent = tree, value = line:sub(indent + 1)}
        table.insert(tree.children, branch)
        line = file:read()
    end
    while tree.parent do
        table.sort(tree.children, comp)
        tree = tree.parent
    end
    table.sort(tree.children, comp)
    return tree
end

--if arg[1] then
    --local file = io.open(arg[1])
    local file = io.input()
    if file and file:seek('set', 3) then
        local tree = read(file)
        if tree then
            print_tree(tree)
        else
            print('epic fail...')
        end
    end
--end

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Задачка на сортировку файла
« Ответ #68 : Декабрь 04, 2012, 10:00:48 am »
ntimer luajit.exe -O3 sort_conf.lua < c:\ОтчетПоКонфигурации.txt > c:\ОтчетПоКонфигурации_sort.txt

ETime(   0:00:02.325 ) UTime(   0:00:01.903 ) KTime(   0:00:00.405 )
ITime(   0:00:00.000 )

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Задачка на сортировку файла
« Ответ #69 : Декабрь 04, 2012, 10:53:27 am »
Вот теперь похоже на cpp  :D

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

Попробуй:
strip sort_conf.exe
Y = λf.(λx.f (x x)) (λx.f (x x))

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Задачка на сортировку файла
« Ответ #70 : Декабрь 04, 2012, 10:58:21 am »
Уменьшился до ~600КБ

А потрошить TotalCommander умеет  :)

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Задачка на сортировку файла
« Ответ #71 : Декабрь 04, 2012, 04:40:20 pm »
Защупал под макосью.
Во-первых компилятор clang а не gcc. На удивление он скушал мой исходник без единого замечания. Ничего менять не пришлось.

Во-вторых результаты забега такие:
с++
$ time ./ilovb_task  < conf.txt > /dev/null

real 0m2.954s
user 0m2.826s
sys 0m0.121s
Lua:
$ time lua ilovb.lua < conf.txt > /dev/null

real 0m2.935s
user 0m2.742s
sys 0m0.187s

Короче, одинаковые результаты :-) Впрочем, clang пока не может похвастать качественной оптимизацией кода. Он пока в начале пути. Но то что c++11 он уже достаточно хорошо держит (лучше студии) - очень радует.
Y = λf.(λx.f (x x)) (λx.f (x x))