Все задачи

Хронология

19 Nov 2013
Read this article in English: here.

Дело было давно, в 2001 году, осенью. Программист занимался поддержкой веб-сервиса, на котором публиковалась хронологическая лента твитов… Ах нет, Твиттера тогда еще не было. Публиковалась лента новостей или чего-то подобного. Важно то, что записи были отсортированы по времени.

И все было хорошо, пока однажды записи не выстроились вот в таком странном порядке (обратите внимание, что идет за отметкой 10:43):

воскресенье, 05:56
воскресенье, 05:56
воскресенье, 05:58
воскресенье, 05:58
воскресенье, 06:05
воскресенье, 06:23
воскресенье, 06:24
воскресенье, 06:26
воскресенье, 06:26
воскресенье, 06:27
воскресенье, 06:27
воскресенье, 06:27
воскресенье, 06:33
воскресенье, 06:33
воскресенье, 06:34
воскресенье, 06:36
воскресенье, 06:38
воскресенье, 07:18
воскресенье, 07:32
воскресенье, 07:36
воскресенье, 07:47
воскресенье, 07:51
воскресенье, 08:04
воскресенье, 08:11
воскресенье, 08:13
воскресенье, 08:49
воскресенье, 08:56
воскресенье, 09:24
воскресенье, 09:27
воскресенье, 09:30
воскресенье, 09:32
воскресенье, 09:45
воскресенье, 09:50
воскресенье, 10:07
воскресенье, 10:08
воскресенье, 10:09
воскресенье, 10:13
воскресенье, 10:14
воскресенье, 10:16
воскресенье, 10:22
воскресенье, 10:31
воскресенье, 10:36
воскресенье, 10:43
воскресенье, 00:03
воскресенье, 00:05
воскресенье, 00:31
воскресенье, 00:33
воскресенье, 00:49
воскресенье, 01:08
воскресенье, 01:19
воскресенье, 01:31
воскресенье, 01:32
воскресенье, 01:33
воскресенье, 01:38
воскресенье, 02:04
воскресенье, 02:18
воскресенье, 02:18
воскресенье, 02:59
воскресенье, 03:22
воскресенье, 03:24
воскресенье, 03:27
воскресенье, 03:43
воскресенье, 04:20
воскресенье, 04:42
воскресенье, 05:03
воскресенье, 05:13
воскресенье, 05:30
воскресенье, 05:32
воскресенье, 05:37
воскресенье, 05:38
воскресенье, 05:39

Что происходит? В коде точно есть вызов sort, сравнивающий таймстемпы записей!

Подсказка

Показать

perl -le '$x = 9; $y = 10; print $x gt $y ? "$x is greater than $y" : "$y is greater than $x"' 

Подсказка-2

Показать

perl -le '$x = 9; $y = 10; print $x > $y ? "$x is greater than $y" : "$y is greater than $x"'

Подсказка-3

Показать

perl -le 'print scalar localtime(1_000_000_000)'

Разоблачение

Показать

Для Москвы:

> perl -le 'print scalar localtime(1_000_000_000)'
Sun Sep  9 05:46:40 2001

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

У сравнения чисел есть забавная особенность: числа с одинаковым количеством разрядов (знаков) можно сравнивать и арифметически, и лексикографически (как строки), результат будет одинаков.

Однако если числа разной разрядности сравнивать как строки, результат отличается от арифметического сравнения. Странный порядок записей в условии задачи – результат лексикографического сравнения временных отметок.

Маленькая демонстрация, как такое могло получиться:

> perl -le 'print join ", ", sort {$a cmp $b} qw/1 2 9 10 11 12 19 20 29 30 31 99/;'
1, 10, 11, 12, 19, 2, 20, 29, 30, 31, 9, 99

Соответственно, при сортировке новостей использовался вызов вида

@items = sort {$a->{date} cmp $b->{date}} @items;

, хотя следовало бы сделать

@items = sort {$a->{date} <=> $b->{date}} @items;

Лучшие решения прислали читатели Vladimir N. Indik и Кирилл. Здорово!

Написать эту задачу нас побудил рассказ одного нашего коллеги. Спасибо ему за историю ^_^