Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Perl: Общие вопросы > Сортировка двумерного массива

Автор: Gekt0r 23.2.2010, 01:06

Задача следующая.
Есть двумерный массив, очень большой, на несколько тысяч строк
Надо его отсортировать по заданному столбцу О_о
вопрос, как это можно сделать, чтобы было не слишком долго?
Есть идея сделать столбцы строками, и сортировать каждую строку по очереди. Только вот как, у меня знаний не хватает..
Подскажите, плз)

Автор: Gekt0r 23.2.2010, 01:33

так, пока можно не отвечать... Что затупил под вечер, сейчас процесс пошел)

Автор: sir_nuf_nuf 23.2.2010, 12:02

Цитата(Gekt0r @ 23.2.2010, 01:06

)

Есть двумерный массив, очень большой, на несколько тысяч строк

это маааахонький массивчик

Автор: kavkaz 24.2.2010, 19:50

Если я вас правильно понял, то вам нужно преобразование Шварца.
Пример:

Код


my @bigarray = (
    [3,4,5,6,7,8,9],
    [2,3,4,5,6,7,8],
    [1,2,3,4,5,6,7]
);
my @out = map {$_->[0]} sort { $a->[1] <=> $b->[1] } map { [ $_, $_->[0] ] } @bigarray;

Нужно прокомментировать?

Автор: klem4 24.2.2010, 20:01

А зачем вообще мап ?

Код


my @bigarray = (
    [3,4,5,6,7,8,9],
    [2,3,4,5,6,7,18],
    [1,2,3,4,5,6,7]
);

my @out = @bigarray[sort { $bigarray[$a]->[6] <=> $bigarray[$b]->[6] } 0..$#bigarray];

Добавлено через 59 секунд
хотя на самом деле TIMTOWTDI

Автор: wanick 25.2.2010, 02:08

ну или так

Код


my @bigarray = (
    [3,4,5,6,7,8,9],
    [2,3,4,5,6,7,18],
    [1,2,3,4,5,6,7]
);
my @out = sort { $a->[6] <=> $b->[6] } @bigarray;

и не забывай что <=> числовое сравнение
а cmp, выполняет алфавитную сортировку в ASCII-порядке

Автор: amg 25.2.2010, 07:55

Преобразование Шварца здесь в самом деле ни к чему. Это преобразование применяется, когда для получения величины, по которой будет сортировка, нужны времязатратные вычисления. Типичный пример, который обычно приводят - сортировка файлов по времени.

@sorted_files = sort { -M $a <=> -M $b } @files;
При обычной сортировке массива из 1000 файлов медленная операция -M (медленная потому что обращается к диску) будет исполняться около 13000 раз (2*N*ln N).

@sorted_files = map {$_->[0]} sort { $a->[1] <=> $b->[1] } map { [ $_, -M $_ ] } @files;
С преобразованием Шварца -M будет исполняться только 1000 раз (N).

Автор: gcc 25.2.2010, 21:51

а интересно квантовый алгоритм будет ли быстрее работать?

Код


use Quantum::Superpositions;

my @a = (1,2,3,4,5,6,7,8,9,10);      # integers
my @b = (2,4,6,8,10,12,14,16,18,20); # doubled

my @unionAB        = sort { $a <=> $b } eigenstates( any(@a, @b) );
my @intersectionAB = sort { $a <=> $b } eigenstates( any(@a) == any(@b) );
my @differenceAB   = sort { $a <=> $b } eigenstates( any(@a) != all(@b) );

print "@intersectionAB\n";

Автор: sir_nuf_nuf 28.2.2010, 12:08

Цитата(gcc @ 25.2.2010, 21:51

)

а интересно квантовый алгоритм будет ли быстрее работать

не, не будет. У вас же обычный, а не квантовый компьютер, поэтому намного эффективней чем QuickSort вы не получите.

Вообще сортировать двумерный массив по N ому столбцу нужно так:

Код


my @bigarray = (
    [3,4,5,6,7,8,9],
    [2,3,4,5,6,7,8],
    [1,2,3,4,5,6,7]
);
my $N = 3;  # по 4 ому столбцу
@bigarray = sort {$a->[$N] <=> $b->[$N]} @bigarray;

klem4, Заметьте, что массив @bigarray - это массив ссылок (ARRAYREFов),
поэтому при его сортировке никаких тяжелых операций копирования не происходит.
Просто переставляются ссылки (обычные скаляры).

Автор: gcc 28.2.2010, 15:57

sir_nuf_nuf, понтяно, тут вот написано что квантовый алгоритм Гровера быстрее чем любая РСУБД

http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%93%D1%80%D0%BE%D0%B2%D0%B5%D1%80%D0%B0

Автор: mvsgt 28.2.2010, 17:59

Цитата(gcc @ 28.2.2010, 15:57

)

тут вот написано что квантовый алгоритм Гровера быстрее чем любая РСУБД

но алгоритм Гровера не даст точного результата, в отличии от РСУБД.
Кстати, в Википедии ничего про РСУБД и не сказано smile

Автор: gcc 2.4.2010, 06:39

кстате, это все таки интересная штука Quantum::Superpositions;

получается поиск по массиву быстрее чем map foreach grep exists (хеш) void у любом случае...

этов mod_perl:
(в CGI будет другие цифры, наверное)

Код


use Quantum::Superpositions;

sub ha2 : Private {
    my ( $self, $c ) = @_;
    
my $hh = {'moder_se' => 1,
                                                  'moder_co' => 1,
                                                  'add_co' => 1,
                                                  'add_se' => 1,
                                                  'moder_user' => 1,
                                                  'admin_user' => 1,
                                                  'super_admin_user' => 1
                                                  
};    

 # print '1' if ( $hh->{moder_se});

# map foreach grep exists void
 print grep  
    $_ eq 'moder_se'
    , @{$c->user->{roles}};
  

    
 }


sub qm : Private {
    my ( $self, $c ) = @_;
 
   
print '7'       if ( 'moder_se' eq any (@{$c->user->{roles}}) );
    
    
}

Код



|  -> /ha2                                                   | 0.014492s |
|  -> /qm                                                    | 0.002837s |

Добавлено @ 06:44
mvsgt, ну там по ссылке вроде бы написано что нету других алгоритмов... А по другой ссылке написано, что будет быстрее чем база данных http://www.opennet.ru/docs/RUS/perl_obzor/files/quantium.html