Задачка на сортировку файла

[valexey_u]

И еще одна особенность моего алгоритма:
Я не сортирую первый уровень. Ибо не надо. На тех файлах всегда 1 корневой элемент.

А мне показалось, что проще написать без исключений из общего правила.

[ilovb]

Еще любопытный момент:
То место где наши алгоритмы расходятся у тебя отрабатывает логически правильнее. Но мой вариант правильнее с точки зрения человека смотрящего в этот текст 

И да, твое решение красивее. В Lua таких абстракций нет.

[ilovb]

И еще одна особенность моего алгоритма:
Я не сортирую первый уровень. Ибо не надо. На тех файлах всегда 1 корневой элемент.

А мне показалось, что проще написать без исключений из общего правила.

Я конкретную задачу решал, на конкретном файле. Просто показалось интересным и решил создать тему. А доводить до общего решения было лень. Я и не тестировал даже. Сделал два прогона на своих файлах и остался удовлетворен результатом 

ps Но довести до ума надо, да...

[valexey_u]

Еще любопытный момент:
То место где наши алгоритмы расходятся у тебя отрабатывает логически правильнее. Но мой вариант правильнее с точки зрения человека смотрящего в этот текст 

И да, твое решение красивее. В Lua таких абстракций нет.

Думаю что на Lua так же сделать можно, то есть ничего не мешает ту же std::multimap реализовать на lua. Это же не вшито в язык у плюсов, это ж просто либа. Лямбды в луа есть. Функции высшего порядка тоже.

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

PS. Кстати, мою программу можно легко ускорить в несколько раз - достаточно заменить multimap на какой-нибудь vector - дело в том, что multimap сортирует по ключам при каждой вставке, что не здорово. А вектора пар можно будет отсортировать один раз непосредственно перед выводом.

[ilovb]

Свои абстракции конечно можно замутить.
Но этого нет из коробки. В этом плане cpp выигрывает у Lua.

[ilovb]

Слушай, valexey, а эту задачу можно решить стандартными юниксовыми утилитами?

[valexey_u]

Слушай, valexey, а эту задачу можно решить стандартными юниксовыми утилитами?

perl/awk/bash - это стандартные утилиты, ими можно? ;-)

В качестве экзотического решения: читаем файло, и по мере чтения создаем структуру каталогов, где названия каталогов - строки из файла. Затем делаем ls дл получившейся структуры каталогов :-D

[ilovb]

Слушай, valexey, а эту задачу можно решить стандартными юниксовыми утилитами?

perl/awk/bash - это стандартные утилиты, ими можно? ;-)

Не, я имел ввиду grep, sort и т.д.

ps В sort я такой опции не нашел.

[ilovb]

В качестве экзотического решения: читаем файло, и по мере чтения создаем структуру каталогов, где названия каталогов - строки из файла. Затем делаем ls дл получившейся структуры каталогов :-D

Прикольно у тебя фантазия работает 
Я б до такого не допетрил 

[ilovb]

valexey, я тут твою прогу скомпилил, и был несколько ошарашен ее размером.
1,39 МБ !    Чего я не так сделал?
А еще больше я удивился когда оказалось, что твоя прога работает не быстрее моей... Это как так?

[valexey_u]

valexey, я тут твою прогу скомпилил, и был несколько ошарашен ее размером.
1,39 МБ !    Чего я не так сделал?

Наверное забыл сделать strip дебажных символов. Примера ради можешь собрать hello world с теми же опциями - будут те же примерно 1.39 Мб.

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

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

PS. Кстати, мою программу можно легко ускорить в несколько раз - достаточно заменить multimap на какой-нибудь vector - дело в том, что multimap сортирует по ключам при каждой вставке, что не здорово. А вектора пар можно будет отсортировать один раз непосредственно перед выводом.

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

[ilovb]

hello world 27 кибибайт всего

Ну а алгоритмы, оптимизации... это понятно. Но скрипт против cpp... Странно это.
Ввод-вывод не узкое место, ибо простое чтение пролетает у меня мгновенно.

[ilovb]

Может в stdin дело?

[valexey_u]

Может в stdin дело?

Поковыряю на досуге (досуг случится после ужина ;-) )

[ilovb]

Может в stdin дело?

Однако нет. У меня через stdin скорость осталась прежней

Код: [Выделить]

function print_tree(tree, indent)
    indent = indent or 0
    for _, branch in ipairs(tree.children) do
        print(string.rep('    ', 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('%s+')
    indent = indent or 0
    local last = indent
    local first = indent
    local tree = {children = {}}
    local branch
    while line do
        _, indent = line:find('%s+')
        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

ps Прилагаю файл на котором тестил (34 МБ)