?

Log in

No account? Create an account

[icon] From inside the Bubble - Lorem Ipsum igitur, juvenes dum sumus
View:Свежие записи.
View:Архив.
View:Друзья.
View:Личная информация.
View:Website (Мой сайт).

Tags:,
Security:
Subject:From inside the Bubble
Time:03:55 pm
Когда-то давно мы оперировали десятками записей, и тогда фиксированный размер массива - 10000 элементов и сортировка этого массива пузырьком (ничем другим в VBA сортировать мы не умели, и O(n^2) не казалось таким уж злом) были нормой. Всё работало, всё всем платилось.

А сегодня этот модуль, к которому не прикасались добрые 10 лет столкнулся с миллионом записей. Даже если бы он смог его поглотить, отсортировать уже не получилось бы. 2013 год, чтоб его. Пришлось в срочном порядке переписать.
comments: Оставить комментарий Previous Entry Поделиться Next Entry


rioman
Link:(Link)
Time:2013-05-30 09:28 pm
А что мешает на VBA быструю сортировку написать?
(Ответить) (Thread)


torrio
Link:(Link)
Time:2013-05-30 09:33 pm
Спроси, что мешало в 2003 году:) Потребности не было, записей было 20 штук, и сортировка пузырьком писалась в 1 строчку.
Потом (довольно скоро, когда от концепции SQL DTS Packages отказались) код был в тупую портирован на C#, снабжен комментарияти типа "/* WOW!"*/ и забыт. Аукнулось вот только что:)
(Ответить) (Parent) (Thread)


elder_george
Link:(Link)
Time:2013-05-30 09:35 pm
Какие люди все-таки бывают трудолюбивые =)

Я бы задолбался переписывать с VBA и заюзал-таки Array.Sort (или аналог).
(Ответить) (Parent) (Thread)


torrio
Link:(Link)
Time:2013-05-30 09:46 pm
Эт что, там еще и сортировка была по дате... конвертированной в строку... лексикографическим сравнением:)
(Ответить) (Parent) (Thread)


elder_george
Link:(Link)
Time:2013-05-30 09:52 pm
Круть =)
(Ответить) (Parent) (Thread)


vgramagin
Link:(Link)
Time:2013-05-30 10:29 pm
По-моему, рекурсивная сортировка слиянием пишется проще, чем пузырьковая. Никакого тебе движения туды-сюды - дели пополам и вызывай сам себя.
(Ответить) (Parent) (Thread)


torrio
Link:(Link)
Time:2013-05-30 10:51 pm
Сейчас уже не помню в подробностях особенности SQL DTS VBA, возможно там были какие-то ограничения на использование функций. Чесслово не помню:)
(Ответить) (Parent) (Thread)


vgramagin
Link:(Link)
Time:2013-05-31 01:44 am
Кстати, отсортировать пузырьком можно и миллион. Времени это, правда, займет. Но можно сделать и в приемлемое.
(Ответить) (Thread)


torrio
Link:(Link)
Time:2013-05-31 02:39 am
Ага, времени это заняло бы слишком много, мы себе такого позволить не можем:(
(Ответить) (Parent) (Thread)


vgramagin
Link:(Link)
Time:2013-05-31 11:54 am
Ну так можно разбить на кластеры, отсортировать кластеры пузырьком, и слить. Непонятно зачем - но, теоретически, можно :-)
(Ответить) (Parent) (Thread)


torrio
Link:(Link)
Time:2013-05-31 02:02 pm
В любой непонятной ситуации разбивай на кластеры!
Разбивай на кластеры, не времени объяснять!
(Ответить) (Parent) (Thread)


elder_george
Link:(Link)
Time:2013-05-31 10:27 pm
Иногда программист может сказать: «Я знаю, как решить эту проблему: я использую разбиение на N кластеров!». После этого у него оказывается N+1 проблема…

=)
(Ответить) (Parent) (Thread)


dfyz
Link:(Link)
Time:2013-05-31 11:11 am
Аналогичный случай был в нашем колхозе. Мы смотрели на пакет для R, который анализирует разладки во временных рядах, и обнаружили там в исходниках вот что: http://pastebin.com/vq8Je3W1
(Ответить) (Thread)


torrio
Link:(Link)
Time:2013-05-31 02:01 pm
Какая прелесть! По объявлению набирали?:)
(Ответить) (Parent) (Thread)


dfyz
Link:(Link)
Time:2013-05-31 03:22 pm
В общем, там использование пузырьковой сортировки оправдано, ибо в этом месте не больше десятка элементов, но сам факт…
(Ответить) (Parent) (Thread)


torrio
Link:(Link)
Time:2013-05-31 04:10 pm
А чего рекурсивную сортировку слиянием не использовали?:) Она ж еще проще пишется (с):)
(Ответить) (Parent) (Thread)


dfyz
Link:(Link)
Time:2013-05-31 04:39 pm
Код в студию. Ставлю шоколадку на то, что по любой разумной метрике простоты написания (хотя бы тупо по количеству строк кода) пузырьковая будет проще.
(Ответить) (Parent) (Thread)


torrio
Link:(Link)
Time:2013-05-31 04:41 pm
Это к vgramagin!
(Ответить) (Parent) (Thread)


dfyz
Link:(Link)
Time:2013-05-31 04:46 pm
Нет уж, привыкай отвечать за чужие слова! Чо как не мужик-то.
(Ответить) (Parent) (Thread)


torrio
Link:(Link)
Time:2013-05-31 04:48 pm
Между прочим, это мой натуральный цвет!
(Ответить) (Parent) (Thread)

[icon] From inside the Bubble - Lorem Ipsum igitur, juvenes dum sumus
View:Свежие записи.
View:Архив.
View:Друзья.
View:Личная информация.
View:Website (Мой сайт).