Лингвофорум

Слепил наколенную поделку для подсчёта количества всевозможных трёхсимвольных сочетаний в массиве текста (300 Мб). Код один в один.
java -client  — 1:50
java -server — 1:26
.NET (с оптимизацией) — 2:19
.NET (без оптимизации) — 2:14 :o

Жаба невозбранно порвала дотнетик. :smoke:

Покажь код. :)

Я тут уже вторую неделю проект на дотнете по работе разрабатываю, наконец-то добрался до си-диеза как следует :)


public class PartsFreq
{     
public static void main(String[] args) throws IOException
{                   
final int                ngram_size = 3;
HashMap<String, Integer> pieces     = new HashMap<String, Integer>();
BufferedReader           r          = new BufferedReader(
new InputStreamReader(System.in, "cp1251"));
String str;
while((str = r.readLine()) != null)
{
for (int pos = 0; pos <= str.length() - ngram_size; pos++)
{
String piece = str.substring(pos, pos + ngram_size);
if (!pieces.containsKey(piece)) pieces.put(piece, 1);
else pieces.put(piece, pieces.get(piece) + 1);
}
}
for(String piece : pieces.keySet())
System.out.printf("%s %d\n", piece, pieces.get(piece));
}
}


class PartsFreq
{     
static void Main()
{                   
var       pieces     = new Dictionary<string, int>();
const int ngram_size = 3;
string    str;
while((str = Console.In.ReadLine()) != null)
{
for(int pos = 0; pos <= str.Length - ngram_size; pos++)
{
string piece = str.Substring(pos, ngram_size);
if (!pieces.ContainsKey(piece)) pieces.Add(piece, 1);
else pieces[piece]++;
}
}
foreach (KeyValuePair<string, int> de in pieces)
Console.Out.WriteLine("{0} {1}", de.Key, de.Value);
}
}


Цитата: RawonaM от ноября 24, 2010, 19:55
си-диеза

До-диеза.

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

Думаю, солнцевская зарулит.

Но решётка таки послаще жабки, да. :)

Цитата: myst от ноября 24, 2010, 20:54
послаще

?

Console.Out.WriteLine
System.out.printf

т.е. тот язык который умеет текст показывать быстрее выигрывает

без текста кажется будет гораздо быстрее

Цитата: iopq от ноября 25, 2010, 07:34
т.е. тот язык который умеет текст показывать быстрее выигрывает

без текста кажется будет гораздо быстрее

Неправильное предположение.

Цитата: Тайльнемер от ноября 25, 2010, 06:49

Цитата: myst от ноября 24, 2010, 20:54
послаще

?

Синтаксический сахар, то, сё. :)

ЦитироватьА мне наоборот не мешает.

а на вики кажут: σύνταξις

Где именно и на что кажут?

На вики статья «синтаксис», а не «синтаксический».

Во-во. А в англе к тому прилагательное syntactic.

Давайте теперь говорить не «тактическое вооружение», а «таксическое», а?‥

Ну и что? Может вы ещё и «грамоту» исправлять будете?

MSVC 2010 (-Ox -GL, линковка с dll'ками) — 1:50. Хи-хи...

MSVC 2010 (-Ox -GL, линковка с dll'ками, -arch:AVX) — 1:35. Жаба совсем близко...

gcc 3.4.4 (cygwin, -O2) — 8:51,45 Прервал не дождавшись конца. :o

Цитата: Dana от ноября 26, 2010, 08:23
Ну и? Из греческого заимствовано существительное «синтаксис».
А «синтаксический» образовано по русским моделям. Cf. фр. syntaxique.

А в принципе в теории было бы нормально и для греч. языка, ибо там в атт. диалекте ti > si (продолжение ПИЕ-шной драмы, как будто). Может, там тоже выравнивание по формам типа -te..., -to... ?

Цитата: myst от ноября 24, 2010, 19:49
Слепил наколенную поделку для подсчёта количества всевозможных трёхсимвольных сочетаний в массиве текста (300 Мб). Код один в один.
java -client  — 1:50
java -server — 1:26
.NET (с оптимизацией) — 2:19
.NET (без оптимизации) — 2:14 :o

Жаба невозбранно порвала дотнетик.

Ну .NET лучше оптимизирован для нормального desktop expierence, поэтому там джиттер послабже будет by design. Поэтому-то мы и не видим жабу на десктопе — ибо слишком много думает.
Но чё-то цифры какие-то подозрительныя. Что такое «с оптимизацией»?

Цитата: myst от ноября 26, 2010, 13:33
gcc 3.4.4 (cygwin, -O2) — 8:51,45 Прервал не дождавшись конца. :o

Чё-то делаешь не так.

Цитата: myst от ноября 24, 2010, 20:12
            if (!pieces.ContainsKey(piece)) pieces.Add(piece, 1);
            else pieces[piece]++;

А что если попробовать как-то так:
int found;
if(!pieces.TryGetValue(piece, out found)) pieces[piece] = 1;
else pieces[piece] = found + 1;

Цитата: Алексей Гринь от ноября 26, 2010, 16:11
Но чё-то цифры какие-то подозрительныя. Что такое «с оптимизацией»?

Цитировать
% csc -\? | grep -i optim
/optimize[+|-]                 Enable optimizations (Short form: /o)

Цитата: Алексей Гринь от ноября 26, 2010, 16:30
Чё-то делаешь не так.

Это не я. Тот же код в VC летает. Там с буферизацией ввода походу фигня какая-то.

Интересно бы ещё через mono 2.8 прогнать (желательно под линюпсем).

Цитата: myst от ноября 26, 2010, 16:40
Там с буферизацией ввода походу фигня какая-то.

Наверное та же фигня у дотнета. Попробуй не перенаправлять ввод и вывод, а указывать данные в args и читать сразу из файла/в файл. Интересно, чё будет.
Но а если поменять код на мой (если он верен, ибо пишу по памяти), то какие цифры будут? Просто интересно.

Цитата: Алексей Гринь от ноября 26, 2010, 16:30
А что если попробовать как-то так:

Цитата: http://msdn.microsoft.com/en-us/library/9tee9ht2.aspx
If the specified key is not found, a get operation throws a KeyNotFoundException

Цитата: myst от ноября 26, 2010, 16:46
If the specified key is not found, a get operation throws a KeyNotFoundException

Это к чему? TryGetValue не кидают ошибку. Вместо этого он возвращает bool.

gcc 4.3.4 такая же фигня. Почти 5 минут ждал.

Цитата: Алексей Гринь от ноября 26, 2010, 16:47
Это к чему?

Цитата: Алексей Гринь от ноября 26, 2010, 16:30
pieces[piece] = 1;

Цитата: μύστηςПочти 5 минут ждал.

Поставь на ночь на закачку ;D.

Цитата: myst от ноября 26, 2010, 16:49

ЦитироватьЭто к чему?

Цитата: Алексей Гринь от Сегодня в 17:30

Цитироватьpieces[piece] = 1;

Так это же не get operation, а set operation.

Цитата: Алексей Гринь от ноября 26, 2010, 16:53
Так это же не get operation, а set operation.

А, ну да. :)

Там скорее всего Substring тормозит, а не таблица.

Ну блин попробуй заменить-то уже.

Цитата: Алексей Гринь от ноября 26, 2010, 16:30
int found;
if(!pieces.TryGetValue(piece, out found)) pieces[piece] = 1;
else pieces[piece] = found + 1;

Кстати, а зачем так? Можно же:

int found;
pieces.TryGetValue(piece, out found);
pieces[piece] = found + 1;


Цитата: myst от ноября 26, 2010, 17:01
Кстати, а зачем так? Можно же:
Код: [Выделить]int found;
pieces.TryGetValue(piece, out found);
pieces[piece] = found + 1;

Можно и так.

Ну дык проигрывает дотнет до сих пор или нет?

А ты прав.
Последний вариант — 1:09. :)

Убрал в жабском коде containsKey:

Integer count = pieces.get(piece);
if(count == null) count = 0;
pieces.put(piece, count + 1);

Стало 0:53. Жабка снова впереди. :)

C++'ный map адово сливает.

Цитата: myst от ноября 26, 2010, 17:33
стало 0:53. Жабка снова впереди. :)

Для полного счастья надо сравнить потребление памяти.

Чё-то короче не так тут. Ибо в жабовской версии идёт тормозной боксинг по несколько раз. Или неужели в дотнете словарь такой тормозной.

Короче, в производительность входит также и потребление памяти. А вот тут прозреваю содомию :\

У серверной машины максимум где-то в районе 190 мегов. У клиентской — 35, но она работает полторы минуты.
У дотнетовой программы — 13,5.

В производительность входит количество работы в единицу времени. :)

.NET'овые программы нельзя никак потюнить, чтобы они, когда надо, память не экономили и выдавали максимальную скорость? Жабомашину можно настраивать по-всякому, и это плюс.

Цитата: myst от ноября 27, 2010, 08:51
.NET'овые программы нельзя никак потюнить, чтобы они, когда надо, память не экономили и выдавали максимальную скорость?

Да там есть конфигурационные файлы какие-то, не разбирался.

Цитата: myst от ноября 27, 2010, 08:51
У серверной машины максимум где-то в районе 190 мегов. У клиентской — 35, но она работает полторы минуты.
У дотнетовой программы — 13,5.

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

Ну вот. Дотнет медленнее в два раза серверной версии, зато потребляет ресурсов меньше в 14 раз. Поэтому он выигрывает.

С hash_map C++ — 1:10. Максимальное потребление памяти ок. 9 мегабайт.

Цитата: Алексей Гринь от ноября 27, 2010, 09:43
Дотнет медленнее в два раза серверной версии, зато потребляет ресурсов меньше в 14 раз.

Дык, не в два: 0:53 vs 1:09

Цитата: myst от ноября 27, 2010, 09:54
С hash_map C++ — 1:10. Максимальное потребление памяти ок. 9 мегабайт.

Очорт! Я забыл отладочный вывод закомментировать. Без него — 0:35. Наконец-то всё встало на свои места. :)

Если размер алфавита около 100 или меньше, то для подсчёта числа различных трёхбуквенных сочетаний проще обойтись прямой индексацией, т. е. массивом вида count[C][C][C], C - размер алфавита. Если же нужен хэш, то тогда можно написать несложный самопальный, который будет быстрее hash_map'а. Использование std::string'а в данном случае не даёт особых удобств, поэтому можно (для оптимизации по времени) юзать массив символов фиксированной длины.

Цитата: GaLL от ноября 27, 2010, 11:45
Если размер алфавита около 100 или меньше, то для подсчёта числа различных трёхбуквенных сочетаний проще обойтись прямой индексацией, т. е. массивом вида count[C][C][C], C - размер алфавита.

Чем проще?

Цитата: GaLL от ноября 27, 2010, 11:45
Если же нужен хэш, то тогда можно написать несложный самопальный, который будет быстрее hash_map'а.

Ога, ради экономии пары секунд только самопала и не хватало. И это нечестно по отношению к конкурентам. Там искаробочные решения.

Цитата: GaLL от ноября 27, 2010, 11:45
Использование std::string'а в данном случае не даёт особых удобств, поэтому можно (для оптимизации по времени) юзать массив символов фиксированной длины.

Конечно, не даёт. Мы же длину строки узнаём из астрала, а автоматическое управление памятью — это неудобно.

Цитировать
Чем проще?

Возможно, мне следовало так выразиться: просто в реализации и эффективнее по времени работы.

Цитировать
Ога, ради экономии пары секунд только самопала и не хватало. И это нечестно по отношению к конкурентам. Там искаробочные решения.

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

Цитата: myst от ноября 27, 2010, 13:44
Конечно, не даёт. Мы же длину строки узнаём из астрала, а автоматическое управление памятью — это неудобно.

Я об этом:

string piece = str.Substring(pos, ngram_size);

Не из какого астрала мы длину строки тут не узнаём, она же равна ngram_size.

Цитата: GaLL от ноября 27, 2010, 13:53
Возможно, мне следовало так выразиться: просто в реализации и эффективнее по времени работы.

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

Цитата: GaLL от ноября 27, 2010, 13:53
Куда больше пары секунд для таких больших данных.

Из этих 35 секунд половина — чтение данных.

Цитата: GaLL от ноября 27, 2010, 13:53
Не понимаю, чего плохого в реализации тех или иных алгоритмов, если это занимает пять минут и если действительно есть смысл оптимизировать.

Знаем мы эти программистские 5 минут, плавно превращающиеся в человеко-часы. :green:
За эти пять минут самое медленное искаробочное решение отработает 2 раза.

Цитата: GaLL от ноября 27, 2010, 13:53
Я об этом:

Код Выделить Развернуть

string piece = str.Substring(pos, ngram_size);
Не из какого астрала мы длину строки тут не узнаём, она же равна ngram_size.


То есть Вы предлагаете вручную выделять массивы символов в куче и копировать в них? И где здесь профит?

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

Я сделал специальную оговорку:

Цитировать
Если размер алфавита около 100 или меньше

Цитировать
трёхбуквенных сочетаний

Если же число возможных подстрок слишком велико, конечно, надо хэш.

Цитировать
Знаем мы эти программистские 5 минут, плавно превращающиеся в человеко-часы. :green:
За эти пять минут самое медленное искаробочное решение отработает 2 раза.

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

Цитировать
То есть Вы предлагаете вручную выделять массивы символов в куче и копировать в них? И где здесь профит?

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

Цитировать
За эти пять минут самое медленное искаробочное решение отработает 2 раза.

За время, ушедшее на обсуждение этой темы участниками - ещё больше раз.
Я просто высказал соображения по поводу возможной оптимизации, решив (вероятно ошибочно), что это действительно имеет отношение к теме и будет кому-то интересно.

Цитата: GaLL от ноября 27, 2010, 14:38
Я сделал специальную оговорку:

Эта оговорка и показывает бессмысленность сей затеи.

Цитата: GaLL от ноября 27, 2010, 14:38
Мне неоднократно доводилось писать самопальный хэш, и ничего близкого к человекочасам не возникало: уж очень прост алгоритм хэширования строк.

Кроме хэширования строк ничего не надо, да? :eat:

Цитата: GaLL от ноября 27, 2010, 14:38
Не будет выделение память под подстроку. Если хэш самопальный, то и копировать эту подстроку необязательно.

А как сами сочетания в результат выводить?

Цитата: GaLL от ноября 27, 2010, 14:38
За время, ушедшее на обсуждение этой темы участниками - ещё больше раз.

Это время тоже часть решения задачи? :o

Цитата: GaLL от ноября 27, 2010, 14:38
Я просто высказал соображения по поводу возможной оптимизации, решив (вероятно ошибочно), что это действительно имеет отношение к теме и будет кому-то интересно.

Ваши соображения по оптимизации были бы интересны для более общей задачи, где размер сочетания переменный. Если Вы с C++ (точнее с микрософтовской реализацией) хорошо знакомы, то, может, подскажете, как выключить синхронизацию в библиотеке. Они однопоточную библиотеку выкинули зачем-то, а судя по показаниям профилёра, как раз на одной из блокировок съедается куча времени. :(