Страницы: 1
RSS
Как ускорить ВПР? (нужен очень быстрый поиск в отсортированной таблице)
 
Суть: есть большая (~100 тыс. строк) таблица, левая колонка - уникальные числа, отсортированные в порядке возрастания, возможны "дырки" (пропущенные значения).  
 
Проблема: сейчас для поиска по таблице используется ВПР(знач, табл, столбец, ИСТИНА).  
Работает как надо, но медленно!! (т.к. ячеек с такими запросами тоже несколько десятков тысяч).  
 
Вопрос: посоветуйте, как принципиально ускорить поиск?
 
Макрос.
"..Сладку ягоду рвали вместе, горьку ягоду я одна."
 
На массивах и словаре.
 
{quote}{login=Владимир}{date=26.04.2012 06:24}{thema=}{post}Макрос.{/post}{/quote}  
 
Несколько лет назад пробовал - макрос на VBA с функциональностью, аналогичной ВПР (полный просмотр таблицы с поиском нужных данных), работал раз в 100(!) медленнее, чем ВПР.
 
Ну так обычно и бывает, если бездумно юзать рекордер.  
Хотя если постараться, то можно написать работающий и в 1000 раз медленнее.  
А можно постараться, и написать работающий в 100 раз быстрее. Образно, такие гонки не устраивал. Но можно попробовать на Вашем файле :)
 
А простой Find с этим не справится?
 
Сомневаюсь я, что на VBA получится сделать аналог ВПР, но побыстрее. Но можете попытаться обогнать С++ на VBA.
Даже самый простой вопрос можно превратить в огромную проблему. Достаточно не уметь формулировать вопросы...
 
Юрий, имхо, простой Find работает простым перебором :)  
 
ВПР на отсортированном списке должен работать бинарным поиском  
но "десятки тысяч" запросов лично меня смущают.  
скорее всего, надо смотреть    
- что это за запросы?;    
- насколько часто их нужно пересчитывать (и все ли одновременно)?;    
- насколько часто менется исходная таблица?    
- нельзя ли разбить исх.таблицу (не фактически, а для формул) на несвязанные поддиапазоны?  
ну и т.д. и т.п.
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
Я знаю, что там тоже перебор, но очень быстрый зато :-)  
А вот несколько десятков тысяч запросов тоже смущают. Что за запросы?
 
Не исключено, что в разных ячейках, содержащих ВПР(), многократно повторяются одни и те же поиски. В этом случае можно поиски выделить в отдельные ячейки с ПОИСКПОЗ() (их будет меньше), а результаты находить  в других при помощи ИНДЕКС()  
ВПР() чувствителен к размеру диапазона-аргумента. Здесь возможна оптимизация посредством ограниченного статического или динамического диапазона (коррекция возможна и с помощью VBA)  
Каскад вычислений желательно проводить по ячейкам сверху-вниз и слева-направо  
Очень нежелательно даные размещать на одном листе, а ВПР() - на другом
 
>Суть: есть большая (~100 тыс. строк) таблица,    
>левая колонка - уникальные числа, отсортированные в порядке возрастания,  
>возможны "дырки" (пропущенные значения).  
---------------------------------  
какова значность чисел 5-8-10-12-больше знаков  
 
 
п.с. примеряю под свою методу поиска до ключа=32000, иногда и больше
 
"Макросом обогнать ВПР()" я подразумевал один макрос vs несколько десятков тысяч ВПР()  
С одной ВПР() гоняться не собираюсь - смысл? Да и как померить?  Запускать обоих 10000 раз в цикле? :)
 
Я ведь, в основном, о зависимых, а не влияющих ячейках...  
 
Формулы подчас таят большие резервы быстродействия  
У Чарльза Вильямса есть примеры оптимизации книги с увеличением быстродействия по-моему, в 1000 раз...  
Возможно, узкое горлышко в другом месте  
Нет ли в книге где-либо СМЕЩ(), ДВССЫЛ(), циклич. ссылок, UDF (особенно, объявленных как volatile)?
 
> есть большая (~100 тыс. строк) таблица, левая колонка - уникальные числа, отсортированные в порядке возрастания  
 
100 тыс. строк - это примерно 300 х 300. Создайте вспомогательный столбец из каждого 300-го числа. Сделайте поиск в 2 этапа - сначала по вспомогательному столбцу определите диапазон из 300 строк, где находится искомое значение, а потом поиск в этом диапазоне.  
В первом приближении получается поиск среди ~600 чисел вместо ~100 тыс.
 
Кстати, только что делал на дружественном форуме задачу - там два листа по 15000 строк, почти одинаковые, нужно сравнить по 4-м столбцам и совместить на новом листе данные из 8-ми других. Причём местами данные в совпадающих ячейках разные (мало, но есть). Такие я писал в итоговую ячейку вместе через разделитель |.  
Это с помощью ВПР() сделать можно, но даже затрудняюсь сказать, сколько ВПР() нужно в одну ячейку втулить (а там выходит 120000 ячеек нужно получить).  
Как вы думаете, сколько времени будет работать ВПР()?  
Время макроса я знаю :)
 
log(100000;2) = 16.609... или ~17
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
ikki это что 17 - минут? секунд? не понял...
 
Господа, я дико извиняюсь - оказывается, в моей книге последний параметр у ВПР был не ИСТИНА, а ЛОЖЬ. Т.е. использовался не бинарный поиск, а полный перебор.  
Сейчас заменил на ИСТИНУ, плюс добавил контроль, что искомый ключ действительно есть - получилось что-то в духе:  
 
Было:  
=ВПР($C$1;$A$1:$B$10000;2;ЛОЖЬ)  
Среднее время работы (для 1 млн. вызовов) - примерно 100 секунд  
 
Стало:  
=ЕСЛИ(ВПР($C$1;$A$1:$B$10000;1;ИСТИНА)=$C$1;ВПР($C$1;$A$1:$B$10000;2;ИСТИНА);НД())  
Среднее время работы (для 1 млн. вызовов) - примерно 1 секунда.  
 
Всем спасибо за интересные идеи!  
Ещё раз, прошу прощения за введение уважаемых гуру в заблуждение.
 
Hugo, 17 - это был ответ Алексею :)  
17 - это макс. кол-во сравнений, необходимых для поиска одного значения в упорядоченнои списке из 100.000 значений.
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
вот, нашел нормальную статью: http://en.wikipedia.org/wiki/Binary_search_algorithm  
а вот здесь гораздо короче, но зато по-русски: http://ru.wikipedia.org/wiki/%C4%E2%EE%E8%F7%ED%FB%E9_%EF%EE%E8%F1%EA  
:)
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
{quote}{login=andy1618}{date=26.04.2012 11:07}{thema=}{post}  
Стало:  
=ЕСЛИ(ВПР($C$1;$A$1:$B$10000;1;ИСТИНА)=$C$1;ВПР($C$1;$A$1:$B$10000;2;ИСТИНА);НД()){/post}{/quote}  
можно ещё ускорить - выполнять поиск один раз.  
см. вложение.
фрилансер Excel, VBA - контакты в профиле
"Совершенствоваться не обязательно. Выживание — дело добровольное." Э.Деминг
 
{quote}{login=ikki}{date=26.04.2012 11:59}  
можно ещё ускорить - выполнять поиск один раз.  
см. вложение.{/quote}  
 
Ага, выше как раз писали про ПОИСКПОЗ + ИНДЕКС.  
Так и буду делать - в моём случае ВПР-ы (с ЛОЖЬю) как раз были натыканы везде, без оглядки на производительность (для небольшой таблицы это работало отлично, а когда данные разрослись на порядок - это стало бутылочным горлышком).  
 
Спасибо!
Страницы: 1
Наверх