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

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

Форум программистов > Perl: Общие вопросы > Сортировка ключей хеша

Автор: Aleshka 31.1.2008, 18:24

Хочу произвести сортировку хеш по ключу.
Ключ имеет такой вид месяц дата, точнее "Jan 15 15:55:11". А как сделать чтобы слово Jan интерепретировалось как первое слово, а feb другое. Другими словами я хочу чтобы если попадается такое перечесление:
Feb 12 12:14:14
Aug 23 13:15:15
Jan 17  20:16:24
Feb  2 13:28:28
То вначале сортировалось по первому слову, т.е после сортировку данные значения принимали следующий вид:
Jan 17  20:16:24
Feb  2 13:28:28
Feb 12 12:14:14
Aug 23 13:15:15
Для  этого мне нужно указать что Jan  это первое  выражение, Feb второе, Mar третье, Apr четвертое и т.д. Вот как это сделать я не знаю и как при этом при сотрировке учитывать остальные значения т.е дату и время???

Автор: tishaishii 31.1.2008, 18:59

Код


my(@a, @b);
sort{
   @a=$a=~/^(\w+)\s+(\d+)\s+(\d+):(\d+):(\d+)/;
   @b=$b=~/^(\w+)\s+(\d+)\s+(\d+):(\d+):(\d+)/;
   # ... выполняешь сравнение и возвращаешь 1, 0 или -1.
   # есть операторы <=> и cmp для этого.
}keys %hash

Автор: ginnie 31.1.2008, 22:09

Уважаемый Aleshka, я бы преобразовал дату в формат ММДДЧЧММСС, тогда с сортировкой проблем не будет, а к нужному формату для вывода преобразовывать после сортировки.

Автор: amg 1.2.2008, 07:02

Код


my @a = ('Feb 12 12:14:14','Aug 23 13:15:15','Jan 17  20:16:24','Feb  2 13:28:28');

my $i = 1;
%M = map {$_=>$i++} qw(Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec);

@a_sorted = sort {norm($a) cmp norm($b)} @a;
print "@a_sorted\n";

sub norm {
  my @t = split /\W+/, $_[0];
  $t[0] = $M{$t[0]};
  return join ' ', map {sprintf '%02d',$_} @t;
}

Автор: ginnie 1.2.2008, 10:30

Уважаемый amg, добавьте в функцию norm() строку

Код


warn $_[0]

и посмотрите, сколько раз она вызовется.

Автор: Aleshka 1.2.2008, 11:58

Спасибо всем за ответы. Amq, а можно подробней узнать некоторые моменты кода??
Функция norm возвращает строку которая состоит из номера месяца цифровое и времени. А вот что делает конструкция :

Код


 map {sprintf '%02d',$_} @t

Для меня остается загадкой.
Qunnie, я добавил данный код

Код


warn $_[0]

Вызвалось оно у меня 8 раз. К чему этот был вопрос и что я не понимаю в данном случае?

Автор: amg 1.2.2008, 12:07

Много. 2NlogN раз примерно. Конечно, гораздо эффективнее было сделать как Вы говорили. Например, заменить строку с сортировкой на две другие:

Код


#@a_sorted = sort {norm($a) cmp norm($b)} @a;
%h = map {$_=>norm($_)} @a;
@a_sorted = sort {$h{$a} cmp $h{$b}} keys %h;

Добавлено через 8 минут и 38 секунд
Aleshka, конструкция map {sprintf '%02d',$_} @t просто добавляет к элементам массива спереди недостающий ноль, чтобы сортировка была правильная, а то 12 будет "меньше", чем 2.

По поводу замечания ginnie см. предыдущий пост.

Автор: Aleshka 1.2.2008, 12:17

Ааа, я понятно к чему вел разговор qinnie, да код который вы amg предложили в данном случае действительно вызвлася всего 4 раза. Только не понятно мне за счет чего было уменьшено их количество?? Можно подробней??

Автор: amg 1.2.2008, 12:38

Цитата(Aleshka @ 1.2.2008, 12:17)

Чтобы осуществить сортировку, необходимо многократно сравнивать элементы массива (N*ln(N) раз в среднем, где N - число сортируемых элементов), и на каждое сравнение в первоначальном коде нужно было дважды вызвать довольно медленную функцию. В исправленном коде эта функция вызывается только раз для каждого элемента массива, а сортировка ведется по значениям хэша (доступ к элементам хэша очень быстр). Поэтому исправленный алгоритм эффективнее (но заметно это будет на весьма больших массивах).

Автор: ginnie 1.2.2008, 12:41

Уважаемые, я не виноват smile

, так в Perl Cookbook написано, поэтому советую всем почаще в нее заглядывать.

Автор: amg 1.2.2008, 13:01

Цитата(ginnie @ 1.2.2008, 12:41)

Уважаемые, я не виноват smile

ginnie, так Вас, вроде никто и не обвиняет. Напротив, с моей стороны Ваше замечание было названо совершенно верным и отмечено плюсиком.

Автор: Aleshka 12.3.2008, 18:22

А не подскажите в тему про сортировку хэшей, меня интересует не решение, а совет. Спасибо, всем кто ответил, получил массу полезной информации. Есть хэш хэшей, которые я хочу отсортировать по сложному критерию, об этом я спрашивал выше.
Проблема в том что хочу по возможности оптимизировать поиск.
Для пояснения приведу свой пример,

Код



%total =(Feb 12 12:14:14 => {
                  come =>"home"
               }
                Aug 23 13:15:15 => {
                come => "work"
               }
                Jan 17  20:16:24 =>{
                come =>"travel" 
                }
               Feb  2 13:28:28 =>{
               come => "husband"
               }
)

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

Автор: ginnie 12.3.2008, 18:39

Aleshka, как вариант, можно в массив поместить не ключи хеша, а ссылки на массивы, в которых первый элемент - дата, второй - ссылка на хэш. Но такой вариант ничем не лучше того, о котором написали Вы, а даже хуже т.к. сначала сортируются ключи хеша, затем все элементы переносятся в массив, после чего данные из массива используются для дальнейшей обработки.
Если хеш Вами используется для объединения данных по датам, то лучшего варианта я Вам предложить не могу.