Пытался понять почему тормозит программа, в итоге нашел проблему в очень неожиданном месте — функция NList.Concat. Она работает ужасающее медленно. Моя реализация, которая работает достаточно быстро приведена ниже:

MyConcatRev[T] (l:list [list [T]]):list[T]
{
    NList.FoldLeft(l, [], NList.FoldLeft(_, _, _::_))
}

MyConcat[T] (l:list [list [T]]):list[T]
{
    NList.Rev(MyConcatRev(l))
}

В догонку... Было бы неплохо провести ревизию билиотечного кода на предмет подобных засад.

Здравствуйте, Ka3a4oK, Вы писали:

KK>Пытался понять почему тормозит программа, в итоге нашел проблему в очень неожиданном месте — функция NList.Concat. Она работает ужасающее медленно. Моя реализация, которая работает достаточно быстро приведена ниже:

Откровенно говоря списки конкатенировать (в узких местах программы) вообще нельзя. Если появляется такая необходимость, то лучше взять SCG.List[T] и в конце преобразовать результат в список (если надо).

Здравствуйте, Ka3a4oK, Вы писали:

KK>Пытался понять почему тормозит программа, в итоге нашел проблему в очень неожиданном месте — функция NList.Concat. Она работает ужасающее медленно. Моя реализация, которая работает достаточно быстро приведена ниже:

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

VD>Откровенно говоря списки конкатенировать (в узких местах программы) вообще нельзя. Если появляется такая необходимость, то лучше взять SCG.List[T] и в конце преобразовать результат в список (если надо).

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

Я сделал так:

def ReadFileStringByString():list[string]
{
    ...
}

NList.RemoveDuplicates
(    NList.Sort
    (    NList.Map
        (    NList.Concat
            (    NList.Map
                (    ReadFileStringByString(),    
                    TokenizeString(_, char.IsLetterOrDigit)
                )
            ),
            _.ToLower()
        ),
    string.Compare
    )
);

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

Здравствуйте, Ka3a4oK, Вы писали:

KK>Я на коленке собрал алгоритм, который бы по текстовому файлу строил его словарь -> лексиграфически упорядоченый список токенов.

KK>Я сделал так:
KK>

KK>NList.RemoveDuplicates...Sort...Map...Concat...Map...
KK>

KK>Мне не нужна была максимальная скорость, иначе бы я использовал С++.

Плюсы тут ровным счетом ничего не дадут. При правильной реализации все урпется в винт.

Я бы для данной задачи воспользовался бы хэш-таблицей или вообще линковским Distinct-том, а он уже сам бы hesh-Set использовал бы.

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

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

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, Ka3a4oK, Вы писали:

KK>>Я на коленке собрал алгоритм, который бы по текстовому файлу строил его словарь -> лексиграфически упорядоченый список токенов.

KK>>Я сделал так:
KK>>

KK>>NList.RemoveDuplicates...Sort...Map...Concat...Map...
KK>>

KK>>Мне не нужна была максимальная скорость, иначе бы я использовал С++.

VD>Плюсы тут ровным счетом ничего не дадут. При правильной реализации все урпется в винт.

VD>Я бы для данной задачи воспользовался бы хэш-таблицей или вообще линковским Distinct-том, а он уже сам бы hesh-Set использовал бы.

Hash не сортирует. В итоге все это потом опять сливать в последовательность из сортиовать.


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

VD>Ну, тогда списки тебе попросту не нужны. Или преобразуй к ним уже готовую последовательность.

Не понял. Почему не нужны? А что нужно?

Просто мне непонятно, почему Concat тут не к месту — это лишь O(n) операция(как и остальные Map-ы в алгоритме), тогда как сортировка, без которой не обойтись — это O(n*log(n)).

Здравствуйте, Ka3a4oK, Вы писали:

KK>Hash не сортирует. В итоге все это потом опять сливать в последовательность из сортиовать.

Ну, и что? Это копейки.

KK>Не понял. Почему не нужны? А что нужно?

Я уже сказал, что проще всего просто вызвать Distinct, а потом OrderBy, если надо.

Здравствуйте, Ka3a4oK, Вы писали:

KK>Просто мне непонятно, почему Concat тут не к месту — это лишь O(n) операция(как и остальные Map-ы в алгоритме), тогда как сортировка, без которой не обойтись — это O(n*log(n)).

А зачем здесь она? У тебя какая задача? Получить список уникальных значений и отсортировать его (как я понял). Ну, так и надо ее решать самыми простыми средствами. Все хорошо к месту.

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, Ka3a4oK, Вы писали:

KK>>Пытался понять почему тормозит программа, в итоге нашел проблему в очень неожиданном месте — функция NList.Concat. Она работает ужасающее медленно. Моя реализация, которая работает достаточно быстро приведена ниже:

VD>Народ, зокомитьте кто-нить. И проверьте есть ли тесты для этой функции.

Стоит ли ConcatRev выносить в публичный доступ ?

Здравствуйте, _nn_, Вы писали:

__>Стоит ли ConcatRev выносить в публичный доступ ?

Стоит. Там где порядок не важен он позволит ускорить алгоритм. К тому же прецеденты есть (MapRev).

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, _nn_, Вы писали:

__>>Стоит ли ConcatRev выносить в публичный доступ ?

VD>Стоит. Там где порядок не важен он позволит ускорить алгоритм. К тому же прецеденты есть (MapRev).

Может в подобныее методы добавить дополнительный параметр со значением по-умолчанию. Что-то типа:

Map(..., KeepOrder:bool=true)
Concat(..., KeepOrder:bool=true)

Старый код при этом скомпилируется.

Здравствуйте, Ka3a4oK, Вы писали:

KK>В догонку... Было бы неплохо провести ревизию билиотечного кода на предмет подобных засад.

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

Автор: Klapaucius
Дата: 28.07.10

.

Здравствуйте, VladD2, Вы писали:

VD>Стоит. Там где порядок не важен он позволит ускорить алгоритм. К тому же прецеденты есть (MapRev).

Ну, в данном случае ConcatRev == Concat |> Rev.

Здравствуйте, Ka3a4oK, Вы писали:

KK>Может в подобныее методы добавить дополнительный параметр со значением по-умолчанию.

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

Здравствуйте, catbert, Вы писали:

VD>>Стоит. Там где порядок не важен он позволит ускорить алгоритм. К тому же прецеденты есть (MapRev).

C>Ну, в данном случае ConcatRev == Concat |> Rev.

Все с точностью до наоборот. ConcatRev можно реализовать эффективно, а уже Concat реализовать через него и Rev.