Среда, 7 Апреля 2004 г.
14:57 Визуальное программирование
Вот написал предыдущую запись и подумал: "Ну и чем тут гордиться?"
Может, и правда переметнуться в стан тех, кто утверждает, что виной всему Дельфи, что её красивости отучают людей программировать? Ведь если реализовывать всё с нуля - предложенное мной решение просто напрашивается. Я его лишь реализовал на Дельфи. Проблема в том, что стандартные компоненты Дельфи настолько удобные (как в плане интерфейса, так и в плане реализации), что обычно стараешься найти не лучший метод решения, а наиболее удобный способ привязать задачу к стандартным компонентам. И лишь когда сталкиваешься с фактом, что стандартные решения не обеспечивают приемлемой скорости, начинаешь действительно программировать.
Но я всё-таки не буду валить с больной головы программиста на здоровую голову Дельфи. Во-первых, это стандартная беда всех высокоуровневых языков (сред) программирования с обилием стандартных решений, к которым относятся и Borland C++ Builder, и MS Visual C++, не говоря уже о всяких Java. А во-вторых, корень зла коренится, как мне кажется, не в улучшении среды программирования, а в увеличении мощности процессора. Ну зачем тратить дни на то, чтобы функция, вызываемая пользователем не в цикле, работала на порядок быстрее, когда времена её работы составляют 0,1 с? Всё равно никто ничего не заметит. А вот когда эти времена уже порядка 100 с, приходится думать головой.
Может, и правда переметнуться в стан тех, кто утверждает, что виной всему Дельфи, что её красивости отучают людей программировать? Ведь если реализовывать всё с нуля - предложенное мной решение просто напрашивается. Я его лишь реализовал на Дельфи. Проблема в том, что стандартные компоненты Дельфи настолько удобные (как в плане интерфейса, так и в плане реализации), что обычно стараешься найти не лучший метод решения, а наиболее удобный способ привязать задачу к стандартным компонентам. И лишь когда сталкиваешься с фактом, что стандартные решения не обеспечивают приемлемой скорости, начинаешь действительно программировать.
Но я всё-таки не буду валить с больной головы программиста на здоровую голову Дельфи. Во-первых, это стандартная беда всех высокоуровневых языков (сред) программирования с обилием стандартных решений, к которым относятся и Borland C++ Builder, и MS Visual C++, не говоря уже о всяких Java. А во-вторых, корень зла коренится, как мне кажется, не в улучшении среды программирования, а в увеличении мощности процессора. Ну зачем тратить дни на то, чтобы функция, вызываемая пользователем не в цикле, работала на порядок быстрее, когда времена её работы составляют 0,1 с? Всё равно никто ничего не заметит. А вот когда эти времена уже порядка 100 с, приходится думать головой.
Комментарии [8]
13:08 В Вилларибо уже танцуют...
Сейчас лопну от гордости.
В общем, решил я сегодня от скуки (работать не хочется, хотя и надо) продолжить свои эксперименты с сортировкой. Начну сразу с конца, то есть с таймингов (на одной и той же машине, сортировка одной и той же таблицы по одному и тому же столбцу).
Итак, есть три варианта программы.
Вариант 1. Неоптимизированный. t=20,7 с.
Вариант 2. После первой оптимизации. t=13,8 с.
Вариант 3. После второй оптимизации. t=5,5 с.
Теперь подробнее. Первую оптимизацию я уже описывал. Она заключалась в уменьшении памяти и ускорения обмена строк после сортировки. В этом мне ещё помог Timoty. Свою лепту внёс, я полагаю, и механизм обмена не по ячейкам, а по строкам.
Вторая оптимизация заключалась в изменении компонента TStringList.
Первоначальная идея состояла в том, чтобы использовать сортировку слиянием вместо быстрой сортировки для получения устойчивого алгоритма сортировки. Точнее, изначально я просто добавлял новые строки с объектами в отсортированный список, так что быстрой сортировкой тут и не пахло. Конечно, можно было добавлять новые строки не с начала, а с конца таблицы, и получить тем самым вроде устойчивый алгоритм. Но устойчив он при этом был бы лишь относительно - где гарантия, что в следующих версиях Дельфи место вставки в отсортированный список не изменится (сейчас строка вставляется в первую позицию из возможных)?
Для этого нужно было написать новый класс, ибо потомки существующего класса TStringList не имеют доступа к внутреннему списку FList, доступ к которому необходим, чтобы не осуществлялась проверка границ массива (что замедляет работу). Тогда я решил, что раз я всё равно делаю новый класс, почему бы мне не изменить тип линкуемых к строке переменных. Вместо объекта (который надо сначала создавать, потом удалять - целая морока) использовать просто целое число - мне ведь нужен только номер строки.
Сделав это и отсортировав список не сразу (в процессе добавления), а после его заполнения, я получил тот же тайминг, что и для варианта 3. Проанализировав, я понял, что получен он в основном за счёт быстроты используемой по умолчанию быстрой сортировки. Устойчивости тут не было и в помине, но переходить к сортировке слиянием с её затратами памяти и огромным числом перемещений элементов из списка в список мне очень не хотелось.
И тут в голову пришла счастливая идея. Раз я всё равно использую этот компонент только для своей задачи, то устойчивость возникает автоматически, если в процедуре сравнения элементов при равенстве строк вставить сравнение прилинкованных целых чисел (в моём случае - номеров строки). Voila! Получаем устойчивую сортировку!
Дальнейшие улучшения возможны только при изменении самого компонента TStringGrid. Я постараюсь изменить его для ускорения открытия файла, что сейчас является самым неприятным (по времени) местом программы. Тогда и посмотрим, насколько это повлияет на сортировку.
В общем, решил я сегодня от скуки (работать не хочется, хотя и надо) продолжить свои эксперименты с сортировкой. Начну сразу с конца, то есть с таймингов (на одной и той же машине, сортировка одной и той же таблицы по одному и тому же столбцу).
Итак, есть три варианта программы.
Вариант 1. Неоптимизированный. t=20,7 с.
Вариант 2. После первой оптимизации. t=13,8 с.
Вариант 3. После второй оптимизации. t=5,5 с.
Теперь подробнее. Первую оптимизацию я уже описывал. Она заключалась в уменьшении памяти и ускорения обмена строк после сортировки. В этом мне ещё помог Timoty. Свою лепту внёс, я полагаю, и механизм обмена не по ячейкам, а по строкам.
Вторая оптимизация заключалась в изменении компонента TStringList.
Первоначальная идея состояла в том, чтобы использовать сортировку слиянием вместо быстрой сортировки для получения устойчивого алгоритма сортировки. Точнее, изначально я просто добавлял новые строки с объектами в отсортированный список, так что быстрой сортировкой тут и не пахло. Конечно, можно было добавлять новые строки не с начала, а с конца таблицы, и получить тем самым вроде устойчивый алгоритм. Но устойчив он при этом был бы лишь относительно - где гарантия, что в следующих версиях Дельфи место вставки в отсортированный список не изменится (сейчас строка вставляется в первую позицию из возможных)?
Для этого нужно было написать новый класс, ибо потомки существующего класса TStringList не имеют доступа к внутреннему списку FList, доступ к которому необходим, чтобы не осуществлялась проверка границ массива (что замедляет работу). Тогда я решил, что раз я всё равно делаю новый класс, почему бы мне не изменить тип линкуемых к строке переменных. Вместо объекта (который надо сначала создавать, потом удалять - целая морока) использовать просто целое число - мне ведь нужен только номер строки.
Сделав это и отсортировав список не сразу (в процессе добавления), а после его заполнения, я получил тот же тайминг, что и для варианта 3. Проанализировав, я понял, что получен он в основном за счёт быстроты используемой по умолчанию быстрой сортировки. Устойчивости тут не было и в помине, но переходить к сортировке слиянием с её затратами памяти и огромным числом перемещений элементов из списка в список мне очень не хотелось.
И тут в голову пришла счастливая идея. Раз я всё равно использую этот компонент только для своей задачи, то устойчивость возникает автоматически, если в процедуре сравнения элементов при равенстве строк вставить сравнение прилинкованных целых чисел (в моём случае - номеров строки). Voila! Получаем устойчивую сортировку!
Дальнейшие улучшения возможны только при изменении самого компонента TStringGrid. Я постараюсь изменить его для ускорения открытия файла, что сейчас является самым неприятным (по времени) местом программы. Тогда и посмотрим, насколько это повлияет на сортировку.
Я жив
[Print]
kv75