Найти одинаковые строки в файле!

[axe]

Раз выкладываем на разных языках

[оффтоп]вот она, "прелесть" C++: на перле все тривиально, на питоне тоже, а вот тут я полминуты фтыкал: где же добавление в map строк, встреченных впервые и это при том, что из 3-х языков я знаю лучше всего именно C++...[/оффтоп]

присоединяюсь к вопросу про производительность: почему эта реализация медленная?

[S.Tokarev]

хочу предупредить что  реализация тормозная до нельзя

Неужели тормознее perl-а? Это не попытка обидеть perl, просто любопытство. Обычно на низкоуровневых языках получается быстрее. Впрочем, мой опыт из области вычислений, а не обработки текста.

Тормоза в темплейте, а не в языке.
"Поиск/доступ" в перле к элементу хеша почти не зависит от заполненности хеша.

[Agafonov]

Тормоза в темплейте, а не в языке.
"Поиск/доступ" в перле к элементу хеша почти не зависит от заполненности хеша.

И что <map> в c++ идиоты не знакомые с быстрыми алгоритмами поиска люди писали?

[Agafonov]

или можно на питоне

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

#!/usr/bin/env python
wr = open('out.txt', 'w')
map(wr.write, set(open('in.txt', 'r').xreadlines()))

in.txt - входящий файл
out.txt - результат

Этот код сохранит порядок строк?

[axe]

Тормоза в темплейте, а не в языке.
"Поиск/доступ" в перле к элементу хеша почти не зависит от заполненности хеша.

И что <map> в c++ идиоты не знакомые с быстрыми алгоритмами поиска люди писали?

видимо, имеется в виду, что <map> - это не хэш-таблица, а бинарное дерево... но imho, разница в скорости доступа O(1) и O(log2(N)) начинает сказываться совсем не на таких объемах данных, которые предполагается обрабатывать...

[Bers]

Этот код сохранит порядок строк?

нет, автору этого и не требовалось

[Yurror]

Да тормознее перла. причем серьёзно тормознее. Наслаждайтесь.
2 S.Tokarev: Тормоза не в темплейтах а в реализации самого <map>. Темплейты там не виноваты.

[S.Tokarev]

Да тормознее перла. причем серьёзно тормознее. Наслаждайтесь.
2 S.Tokarev: Тормоза не в темплейтах а в реализации самого <map>. Темплейты там не виноваты.

Я это и имел ввиду. <map> вроде и есть темплейт. Хотя могу ошибаться.

[Yurror]

Читаем http://google-sparsehash.googlecode.com/svn/trunk/doc/performance.html
Качаем http://google-sparsehash.googlecode.com/files/sparsehash_1.3-1_i386.deb , устанавливаем.
Копируем

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

#include <cstdio>
#include <google/dense_hash_map>

using google::dense_hash_map;
using __gnu_cxx::hash;

struct eqstr
{
  bool operator()(const char* s1, const char* s2) const
  {
    return (s1 == s2) || (s1 && s2 && strcmp(s1, s2) == 0);
  }
};

int main(int argc, char** argv) {
    char *str = NULL;
    size_t sz = 0;

    dense_hash_map<const char*, int, hash<const char*>, eqstr> str_map;
    str_map.set_empty_key(NULL);

    while (getline(&str, &sz, stdin) != -1) {
        int& ref = str_map[str];
        if (!ref) {
            printf("%s", str);
            ref = 1;
        }
    }

    if (!str)
        free(str);

    return (EXIT_SUCCESS);
}
Программа стала примерно в два раза быстрее. Но все равно до перла как до Индии пешком. =(
P.S. у кого есть программка на С/С++ не уступающая perl в скорости?

[Agafonov]

Чёрт, на чём же они написали сам Perl? 

[HoudiniWater]

Мне кажется, что если спрашивают на форуме по линуксу решение какой-то задачи, то не надо давать решение на перле, питоне, руби и хз чем.
Вот простое решение, если файл называется file, то

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

cat file | sort | uniq
и всё, не изобретайте велосипед.

[Yurror]

Блин, HoudiniWater, форум хоть и про Linux и даже конкретнее про дистрибутив Ubuntu, но чем здесь только не занимаются. И этото раздел форума посвящен программированию. Поздравляю! ты рекордсмен! у тебя самое тормозное решение! Еще и порядок строк изменен так что
"Зина, в печку!" (с) довольно известный профессор. Я просил быстрое решение, если ты читать не умеешь. Причем на языке С/С++. Разуй глаза.

Чёрт, на чём же они написали сам Perl? 

Что-то мне подсказывает что там Си. В чистом виде. Значит вообще задачка имеет решение. Но качать весь тарболл с перлом и потом петрушить его...
Если кто-нибудь геройски выполнит сие деяние, прошу выложить решение сюда.
Остальных "героев, кторые не любят изобретать велосипеды" ака HoudiniWater я прошу не беспокоиться. Без вас уже давно справились. Заранее спасибо за понимание.

[wl]

Эхх, раз пошла пьянка с реализациями алгоритма на разных языках...

http://www.99-bottles-of-beer.net/

[HoudiniWater]

Yurror, решение просили, не вы, а lumen_xp, более того было специально оговорено, что сохранение порядка строк не важно.
При всех недостатоков моего решения, оно самое простое из всех и всем будет понятно, и пишется оно за 3 секунды.

Хотя, проверить на скорость мне было бы тоже интересно. Есть уже какой-нибудь тестовый файлик?

[Sova777]

sova@sova:~$ wc -l access_log.30
144898 access_log.30
// C++ с map (первый пример)
sova@sova:~$ time -p ./unify < access_log.30 > /dev/null
real 3.36
user 3.31
sys 0.05
//Perl
sova@sova:~$ time -p perl ./unify.pl < access_log.30 > /dev/null
real 0.70
user 0.64
sys 0.06
//Shell
sova@sova:~$ time -p cat access_log.30 | sort | uniq > /dev/null
real 3.01
user 2.79
sys 0.23