[ /tv/ /rf/ /vg/ /a/ /b/ /u/ /bo/ /fur/ /to/ /dt/ /cp/ /oe/ /bg/ /ve/ /r/ /mad/ /d/ /mu/ /cr/ /di/ /sw/ /hr/ /wh/ /lor/ /s/ /hau/ /slow/ /gf/ /vn/ /w/ /ma/ /azu/ /wn/ ] [ Main | Settings | Bookmarks | Music Player ]

No.9514 Reply
File: computer.jpg
Jpg, 73.19 KB, 852×480 - Click the image to expand
edit Find source with google Find source with iqdb
computer.jpg
Здравствуй, Добрач!

Дело в том, что есть одна задача. Нужно иногда чистить хистори шелла. В том числе вычищать оттуда дублирующиеся строки. При этом порядок оставшихся строк должен сохраняться (поэтому sort | uniq не катит). Строк в хистори у меня много, максимум 100000.

Так вот, с файлом размером около 50тыс. строк проги на го и окемле (с ocamlopt) справляются секунд за 9. Скриптик на питоне -- меньше чем за минуту. А вот скриптик на перле копается две с половиной. В перле я не силён, вот и интересно, може я там фигню написал?

А как бы написал это ты, Доброанон?

Скрипты/сорцы показывать?
>> No.9518 Reply
>>9514
Показывай.

Сколько сорт|юник работает?
>> No.9520 Reply
>> No.9521 Reply
File: 1242401859863.jpg
Jpg, 100.74 KB, 550×524
Your censorship settings forbid this file.
unrated
>>9518
Внезапный медскиллз
cat blah | nl -w10 | sort -k2 | uniq -f1 | sort -nk1 | cut -sf2-
>> No.9522 Reply
В .bashrc напиши
export HISTCONTROL=erasedups
И зачем тебе 100000 уникальных команд - ебанутый штоле? Уменьши размер history

Можно ещё игнорировать некоторые команды
export HISTIGNORE="&:mc:top:exit:mplayer *"
>> No.9528 Reply
File: calculate.jpg
Jpg, 62.87 KB, 852×480 - Click the image to expand
edit Find source with google Find source with iqdb
calculate.jpg
>>9520
>>9522

Да, когда пользовался этим вашим дефолт-шеллом так и делал.
> И зачем тебе 100000 уникальных команд
А почему бы и нет. Кушать они не просят, а глянуть иногда сложнонавороченный one-liner трёхлетней давности бывает удобнее, чем заново изобретать.
Хотя, если регулярно вычищать дубли, одиночные команды и прочий хлам, то 20-30тыс. должно лет на 5 хватить.
>> No.9529 Reply
File: high.jpg
Jpg, 40.07 KB, 852×480 - Click the image to expand
edit Find source with google Find source with iqdb
high.jpg
>>9521
> cat blah | nl -w10 | sort -k2 | uniq -f1 | sort -nk1 | cut -sf2-
А вот это очень круто. Спасибо, возьму на вооружение.
Меньше двух десятых секунды
>> No.9531 Reply
>>9514
Из какой анимы пикчи?
>> No.9533 Reply
File: assemble.jpg
Jpg, 78.41 KB, 852×480
edit Find source with google Find source with iqdb
assemble.jpg
File: histuniq.pl
Pl, 0.00 KB, 0 lines
view edit
histuniq.pl
File: histuniq.py
Py, 0.00 KB, 0 lines
view edit
histuniq.py
File: histuniq.ml
Ml, 0.00 KB, 0 lines
view edit
histuniq.ml

>>9518
> Сколько сорт|юник работает?
Меньше десятой доли секунды.
>> No.9534 Reply
>>9533
Go не понимайт.
package main
import (
    "os"
    "bufio"
)
func read_strs() []string {
    var strs []string
    r := bufio.NewReader(os.Stdin)
    str, err := r.ReadString('\n')
    for err != os.EOF {
        strs = append(strs, str)
        str, err = r.ReadString('\n')
    }
    return strs
}
func write_uniq(strs []string) {
    w := bufio.NewWriter(os.Stdout)
    for i, s := range strs {
        j := i + 1
        for j < len(strs) && strs[j] != s {
            j++
        }
        if j >= len(strs) {
            w.WriteString(s)
        }
    }
    w.Flush()
}
func main() {
    strs := read_strs()
    write_uniq(strs)
}
>> No.9536 Reply
>>9533
Ничего удивительного, у тебя везде квадратичный алгоритм. Тебе нужно строить, например, хештаблицу строка->номер за, а потом сортировать по номеру. В итоге выйдет тот же O(n logn).
>> No.9537 Reply
>>9536
O(n^3), насколько я понимаю
>> No.9538 Reply
>>9537
В смысле у опа O(n^3), а не n^2
>> No.9539 Reply
>>9538
нет, пизжу3
>> No.9540 Reply
>>9533
Перл у тебя проседает потому что ты в 9000 проходов это делаешь
Попробуй, как и советутет >>9536, через хеш. Как-нибудь так:
cat .bash_history | perl -e 'my %hash = (); while(<>){ print and $hash{$_} = "" if not defined $hash{$_} };'
>> No.9542 Reply
>>9540
Да, оп, ты мне подкинул интересную идею. Можно еще добавить проверку на валидность команды, и чистить башхистори по крону. Только я - ленивый мудак, и ничего не сделаю.
>> No.9543 Reply
module H = Hashtbl
module L = List

let tbl_add tbl line n =
  try let _ = H.find tbl line in () with Not_found -> H.add tbl line n

let rec collect_lines n tbl =
  try let line = input_line stdin in
      tbl_add tbl line n; collect_lines (n+1) tbl
  with End_of_file -> tbl

let unique_lines () =
  let to_list tbl = H.fold (fun k v l -> (k,v)::l) tbl [] in
  to_list (collect_lines 1 (H.create 50000))

let sort_by_number = L.sort (fun (k1,v1) (k2,v2) -> v1-v2)

let output = L.iter (fun (l,_) -> output_string stdout (l ^ "\n"))

let _ = output (sort_by_number (unique_lines ()))
>> No.9544 Reply
File: joy.jpg
Jpg, 95.28 KB, 852×480 - Click the image to expand
edit Find source with google Find source with iqdb
joy.jpg
>>9536
>>9543

Спасибо!
Как-то я не подумал, что можно быстрее, чем O(n^2)

Вот так, вроде бы, на Иди должно выглядеть, если кому интересно:
%% ~ 0.15s %%
package main
import (
    "os"
    "bufio"
)
type mapstr map[string]int
func read_strs() (strs []string) {
    r := bufio.NewReader(os.Stdin)
    str, err := r.ReadString('\n')
    for err != os.EOF {
        strs = append(strs, str)
        str, err = r.ReadString('\n')
    }
    return
}
func write_strs(strs []string) {
    w := bufio.NewWriter(os.Stdout)
    for _, s := range strs {
        w.WriteString(s)
    }
    w.Flush()
}
func uniq(strs []string) []string {
    m := make(map[string] int, 50000)
    k := len(strs) - 1
    for i := k; i >= 0; i-- {
        _, ok := m[strs[i]]
        if !ok {
            m[strs[i]] = k
            k--
        }
    }
    uniq_strs := make([]string, len(m))
    for s, i := range m {
        uniq_strs[i - k - 1] = s
    }
    return uniq_strs
}
func main() {
    strs := read_strs()
    write_strs(uniq(strs))
}
>> No.9545 Reply
File: rising_sun.jpg
Jpg, 53.48 KB, 852×480 - Click the image to expand
edit Find source with google Find source with iqdb
rising_sun.jpg
>>9544
Кстати, пробовал сначала сделать, как у 9521-куна, но программно.
т.е. добавить ключ, отсортировать по строкам, убрать дубли, отсортировать снова по ключу
Получилось тоже довольно быстро, точно лучше, чем первый вариант.

>>9540
>>9542
> чистить хистори по крону
Да, именно такая идея и была, в т.ч. и проверка на валидность.
Вопрос, почему перловый скрипт у меня получился такой медленный при том же алгоритме, остался открытым. Ну да ладно.
>> No.9546 Reply
>>9545
> Вопрос, почему перловый скрипт у меня получился такой медленный при том же алгоритме, остался открытым. Ну да ладно.
Например лишние аллокации/копирование. Как реализован shift? Не будет ли он при каждом обращении перезаписывать все элементы на 1 ячейку левее?
>> No.9547 Reply
>>9543
До меня только что дошло, что можно проще. Сложность та же, но код проще и короче:
module L = List
module S = Set.Make(struct type t = string let compare = compare end)

let unique_lines () =
  let rec loop set lst =
    try let line = input_line stdin in
        if S.mem line set
        then loop set lst
        else loop (S.add line set) (line::lst)
    with End_of_file -> lst
  in L.rev (loop S.empty [])

let _ = L.iter (fun l -> output_string stdout (l ^ "\n")) (unique_lines())
>> No.9548 Reply
File: gun.jpg
Jpg, 39.89 KB, 852×480 - Click the image to expand
edit Find source with google Find source with iqdb
gun.jpg
>>9547
Ну тогда уж я добавлю ещё одно небольшое условие, из-за которого пришлось немного поизвращаться тут >>9544
Дублирующиеся строки должны удаляться с начала файла, а не с конца.
Т.е. (a b c d b c e) -> (a d b c e), а не (a b c d e)
>> No.9549 Reply
>>9548
Ну в этом случае нужно допиливать первый вариант:
let tbl_add tbl line n =
  try let _ = H.find tbl line in () with Not_found -> H.add tbl line n
превратится просто в
H.replace tbl line n
Олсо, сортировку везде (включая мой первый шеллскрипт) надо заменить на стабильную, иначе будет хуита.
>> No.9551 Reply
File: fork.jpg
Jpg, 72.26 KB, 852×480 - Click the image to expand
edit Find source with google Find source with iqdb
fork.jpg
>>9549
Однако же
tac hist1 | nl -w10 | sort -k2 | uniq -f1 | sort -nk1 | cut -sf2- | tac > hist2
и
tac hist1 | nl -w10 | sort -s -k2 | uniq -f1 | sort -nk1 | cut -sf2- | tac > hist2
работают одинаково правильно.

Или я что-то недопонял про стабильную сортировку?
>> No.9553 Reply
>>9545
> Перл у тебя проседает потому что ты в 9000 проходов это делаешь
Во первых, ты копируешь весь инпут в переменную. Если там действительно много всего, то это уже существенно. Во вторых, ты без конца передаешь этот массив в какую-то левую не библиотечную функцию, причем передаешь не ссылкой, т.е. твой массив копируется $#lines+1 раз(хотя элементов с каждым разом все меньше, да).
Да, расскажи сколько получается с >>9540 У меня получалось 0.017, но у меня хистори маленькая.

А питоновский скрипт тоже можно чуть пересмотреть. Из видимых оптимизаций без изменения структуры использование print вместо sys.stdout.write, или сделать переменную-алиас для sys.stdout.write. Будет меньше разрешений имен в каждой итерации, иногда даже значительный прирост дает. Ну и опять же ты слайсом без конца копируешь массив и итерируешь по нему.
>> No.9554 Reply
File: 1277997069.jpg
Jpg, 148.90 KB, 736×736 - Click the image to expand
edit Find source with google Find source with iqdb
1277997069.jpg
>>9553
> передаешь этот массив в какую-то левую не библиотечную функцию
> меньше разрешений имен в каждой итерации, иногда даже значительный прирост дает
ИНТЕРПРЕТАТОРОПРОБЛЕМЫ
>> No.9555 Reply
>>9551
Если оно вдруг сработало как надо, не значит, что всегда будет так.
>> No.9568 Reply
File: robots.jpg
Jpg, 60.90 KB, 852×480 - Click the image to expand
edit Find source with google Find source with iqdb
robots.jpg
>>9553
> расскажи сколько получается с >>9540
Быстро получается. Около десятой секунды.

Эти >>9544, >>9551, >>9547, >>9540 все примерно одинаково быстро работают.
Не все, правда, удовлетворяют условию >>9548.
>> No.9570 Reply
File: 13022023351274.png
Png, 230.01 KB, 459×600 - Click the image to expand
edit Find source with google Find source with iqdb
13022023351274.png
> В том числе вычищать оттуда дублирующиеся строки. При этом порядок оставшихся строк должен сохраняться
У меня для тебя плохие новости, у нормальных людей distinct и group не разрушают сортировку.
Даже если недо-distinct разрушает:
  
let yobaDistinct = Seq.mapi (curry id) >> Seq.distinctBy snd >>  Seq.sortBy fst >> Seq.map snd


Password:

[ /tv/ /rf/ /vg/ /a/ /b/ /u/ /bo/ /fur/ /to/ /dt/ /cp/ /oe/ /bg/ /ve/ /r/ /mad/ /d/ /mu/ /cr/ /di/ /sw/ /hr/ /wh/ /lor/ /s/ /hau/ /slow/ /gf/ /vn/ /w/ /ma/ /azu/ /wn/ ] [ Main | Settings | Bookmarks | Music Player ]