Visual Basic, .NET, ASP, VBScript
Новости | Примеры | Библиотека кодов | НеЧаВо | VBA | Справочник по VB | Справочник по WinAPI | ActiveX контролы | Статьи по VB | Мастерская разработчика | Форум VBNet | Яndex bar! | Голосование | Полезные программы | Магазин VBNet | Рассылка | Конкурсы | Юмор | Чат | Реклама на VBNet | Автора! | Ссылки | Бета-тестирование | Послать пример на сайт
 

   
   
     

Форум - .NET

Страница: 1 | 2 | 3 |

 

  Вопрос: Узнать есть ли элемент в массиве без его переборки Добавлено: 16.02.09 15:18  

Автор вопроса:  Destroyer

Ответить

  Ответы Всего ответов: 35  

Номер ответа: 16
Автор ответа:
 Artyom



Разработчик

Вопросов: 130
Ответов: 6602
  Профиль | | #16 Добавлено: 16.02.09 20:51
Встречный вопрос автору вопроса.
С каким объемом данных приходится работать?

Если массив небольшой, порядка сотни элементов то не советую заморачиваться потому что разница в быстроедйствии между двоичным поиском и перебором будет составлять 3-4 раза. Зато не нужна предварительная подготовка массива.

Да и вообще если вопрос стал чисто теоритически, ясно. А практически - есть тормоза при работе с массивом? Я лично сомневаюсь. Поэтому не нужно оптимизировать там где ничего оптимизировать не нужно.

Ответить

Номер ответа: 17
Автор ответа:
 fAndOrIn



Вопросов: 5
Ответов: 344
  Профиль | | #17 Добавлено: 16.02.09 22:06
Уважаемые корифеи, если конечно не западло. Развейте сомнения, покажите что бинарный поиск быстрее этого (лепил на скорую руку в Ёкселе, поэтому возможны ляпы, но вроде работает)
  1. Option Explicit
  2. Dim A() As String
  3. Dim I As Long, J As Long, C As Long, N As Long
  4. Const U = 2999999
  5. Dim X$, Y$
  6.  
  7. Sub QuickSort(ByVal LBound_A As Long, ByVal UBound_A As Long)
  8. Dim I As Long, J As Long
  9. I = LBound_A: J = UBound_A: X = A((LBound_A + UBound_A) \ 2)
  10. Do
  11.   While A(I) < X: I = I + 1: Wend: While X < A(J): J = J - 1: Wend 'по возрастанию
  12.   If I <= J Then Y = A(I): A(I) = A(J): A(J) = Y: I = I + 1: J = J - 1
  13. Loop Until I > J
  14. If LBound_A < J Then QuickSort LBound_A, J
  15. If I < UBound_A Then QuickSort I, UBound_A
  16. End Sub
  17.  
  18. Sub SearchForArray()
  19.   'забиваем массив всякой хренотенью
  20.   ReDim A(0 To U)
  21.   Randomize
  22.   For I = 0 To U
  23.     For J = 0 To Int(Rnd * 16)
  24.       A(I) = A(I) + Chr$(Int(Rnd * 256))
  25.     Next J
  26.   Next I
  27.   QuickSort 0, U
  28.   'собственно поиск
  29.   Dim b_Yes As Boolean, S$, L As Long, R As Long, T As Single
  30.   T = Timer
  31.   S = A(Int(Rnd * (U + 1)))
  32.   R = U
  33.   Do
  34.     C = (R + L) \ 2
  35.     Select Case StrComp(S, A(C))
  36.     Case -1: R = C
  37.     Case 0: b_Yes = True: Exit Do
  38.     Case 1: L = C
  39.     End Select
  40.   Loop While (R - L) > 1
  41.   Debug.Print Timer - T, S = A(C)
  42. End Sub

Ответить

Номер ответа: 18
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
  Web-сайт: sharpc.livejournal.com
 Профиль | | #18 		Добавлено: 16.02.09 22:34
Это и есть бинарный поиск, вроде.

Ответить

Номер ответа: 19
Автор ответа:
 Artyom



Разработчик

Вопросов: 130
Ответов: 6602
  Профиль | | #19 Добавлено: 16.02.09 22:42
Алгоритм похож на двоичный поиск.
1) Нет прерывания алгоритма в случае если элемент не найден (я так понимаю он будет просто бесконечно долго крутиться в этом случае)
2) (R + L) \ 2 может дать переполнение, если R + L выйдет за границы Long. Насколько я помню, нужно R + (L - R) \ 2

Быстрее чем Array.BinarySearch это работать не будет.

Ответить

Номер ответа: 20
Автор ответа:
 fAndOrIn



Вопросов: 5
Ответов: 344
  Профиль | | #20 Добавлено: 16.02.09 22:56
Ну блин, а я думал: бинарный поиск что-то заумное на уровне ASMа и т.п. Потому и задавал дурацкие вопросы (уж не судите строго). А про этот считал методом половинного деления.
А зацикливания не происходит - проверено. И мне кажется, вряд ли у кого-то из нас есть машины, способные ворочать массивы А(2147483647\2)as string

Ответить

Номер ответа: 21
Автор ответа:
 Ra$cal



ICQ: 8068014 

Вопросов: 18
Ответов: 817
  Web-сайт: www.rascalspb.narod.ru
 Профиль | | #21 		Добавлено: 16.02.09 23:07
это ж как надо написать хэш таблицу, чтобы она ела в 10 раз больше памяти? это ж какой вид таблицы? пример пожалста.

у двоичного поиска тока один серьезный минус - пересортировка в случае добавления элемента. в остальном он удобнее. для случая с активными добавлениям его или надо мутировать (типа запасной список меньшего размера, который ведется отдельно, и слияние с основным тока при выходе из порграммы), либо юзанье хеш таблицы.

но думаю в данном случае число записей не будет создавать проблем для пересортировки.

Ответить

Номер ответа: 22
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
  Web-сайт: sharpc.livejournal.com
 Профиль | | #22 		Добавлено: 16.02.09 23:33
Можно написать хэш-таблицу, которая будет жрать во сколько угодно раз больше памяти, чем надо под ее элементы.

Ответить

Номер ответа: 23
Автор ответа:
 Artyom



Разработчик

Вопросов: 130
Ответов: 6602
  Профиль | | #23 Добавлено: 16.02.09 23:47
fAndOrIn пишет:
А зацикливания не происходит - проверено

Сори, не заметил последнее условие.
Там правда скорее нужно Loop While (R - L) > 0

Ответить

Номер ответа: 24
Автор ответа:
 Ra$cal



ICQ: 8068014 

Вопросов: 18
Ответов: 817
  Web-сайт: www.rascalspb.narod.ru
 Профиль | | #24 		Добавлено: 16.02.09 23:48
да шож такое. никак не расслабицо, везде надо продумывать каждое слово =) кароч надеюсь сарказм шарпа понятен. чтобы закодировать хеш таблицу нам нада структуру. всего из двух полей - хеш от ключа и индекс в массиве того элемента, чей хеш хранится. struct HASH_ITEM{UINT hash; UINT index;};итого для одного элемента таблицы надо 8 байт. реальный минус - таблица должна быть фиксированного размера. поэтому умножаем максимальное число записей на 8 байт. это врядли составит даст прирост поедания памяти в 10 раз =) строки для такого прироста должны быть весьма маленькие ;)

Ответить

Номер ответа: 25
Автор ответа:
 Artyom



Разработчик

Вопросов: 130
Ответов: 6602
  Профиль | | #25 Добавлено: 16.02.09 23:50
Ra$cal пишет:
это ж как надо написать хэш таблицу, чтобы она ела в 10 раз больше памяти? это ж какой вид таблицы? пример пожалста.

System.IO.Dictionary(Of Int32, Byte)

Загонял 10M элементов для теста.

Ra$cal пишет:
но думаю в данном случае число записей не будет создавать проблем для пересортировки.

Я думаю в этом случае число записей не будет создавать проблем и для перебора :)

Ответить

Номер ответа: 26
Автор ответа:
 fAndOrIn



Вопросов: 5
Ответов: 344
  Профиль | | #26 Добавлено: 17.02.09 07:47
Выслушал мнение старших, еще немного помозговал и кажеться, родил...
  1.   Do
  2.     C = L + (R - L) \ 2'чуть-чуть наоброт, уж извини...(хотя,кажется без разницы). Вдруг появятся такие машины...Хотя двойной запас-не выход при нынешних темпах прогресса
  3.     Select Case StrComp(S, A(C))
  4.       Case -1: R = C - 1 'незачем проверять правую границу, если она уже не равна
  5.       Case 1: L = C + 1 'тоже самое про левую
  6.       Case 0: b_Yes = True: Exit Do 'на последнее место(хоть на копейку, но может добавить темпа)
  7.     End Select
  8.   Loop While R >= L 'Loop While (R - L) > 1 мне и самому вчера не понравился, но без нынешних изменений с R и L код не работал.

Теперь кажись всё! Destroyer, принимай заказ...

Ответить

Номер ответа: 27
Автор ответа:
 Sharp


Лидер форума

ICQ: 216865379 

Вопросов: 106
Ответов: 9979
  Web-сайт: sharpc.livejournal.com
 Профиль | | #27 		Добавлено: 17.02.09 11:53
чтобы закодировать хеш таблицу нам нада структуру. всего из двух полей - хеш от ключа и индекс в массиве того элемента, чей хеш хранится. struct HASH_ITEM{UINT hash; UINT index;};итого для одного элемента таблицы надо 8 байт.

У меня сложилось ощущение, что тебе стоит перечитать, что такое хэш-таблица.

Ответить

Номер ответа: 28
Автор ответа:
 Artyom



Разработчик

Вопросов: 130
Ответов: 6602
  Профиль | | #28 Добавлено: 17.02.09 14:55
fAndOrIn, здорово, правда топик-стартеру нужно под .NET, а там все это уже есть - Array.BinarySearch :)

Ответить

Номер ответа: 29
Автор ответа:
 Ra$cal



ICQ: 8068014 

Вопросов: 18
Ответов: 817
  Web-сайт: www.rascalspb.narod.ru
 Профиль | | #29 		Добавлено: 17.02.09 16:20
Sharp, да, хранить хэш в таблице это я чтото тормознул. я просто попутно задумался над разрешением коллизий, плюс время уже =\ я реализовывал это года 2 назад.

Ответить

Номер ответа: 30
Автор ответа:
 Destroyer



Вопросов: 2
Ответов: 3
  Профиль | | #30 Добавлено: 17.02.09 23:16
Всем спасибо, все что хотел узнал из топика :)

Ответить

Страница: 1 | 2 | 3 |

Поиск по форуму



© Copyright 2002-2011 VBNet.RU | Пишите нам