Страница: 1 |
Что-то посмотрел я на Quick Sort и мне показалось что этот метод только усугу[sensored]ет Public Function findFreeCode() As String И ещё будет ли такой вариант цикла работать быстрее(т.е. количество проходов меньше For i = 0 To recCount - 1 step 10 'просмотр массива на присутствие кода FreeCode +1...+10 Павел, спасибо что переслали сообщение. А быстрый поиск я реализовал, использовав метод RS.Sort и вместо массива использовав переменную типа Variant, т.к. переменная заполняется очень быстро и без цикла, на что уходило немало времени. Может кому пригодится: Private function Свободный_Номер() as Double Свободный_Номер=i: Exit Function Помогло наличие RecordSet.Sort и нещадно ругаемая всеми переменная типаVariant. Результат-просмотр 50000 записей в самом неблагоприятном случае занимает ок.2сек. Спасибо всем. Страница: 1 |
Вопрос: Математика
Добавлено: 18.11.03 22:18
Автор вопроса: cresta
Есть набор чисел. Числа двенадцатизначные, расположены в
произвольном порядке. Число элементов в наборе может достигать
нескольких десятков тысяч.Как можно быстро определить минимальное свободное значение,
не встречающееся в наборе?
Например:
311928374667
029384756473
798765432765
.
.
.
319283700919
чтобы получить 029384756474 ( второе значение +1)
Последовательный перебор всех значений набора с последующим сравнением с
каждым значением набора на предмет а=а+1 в самом неблагоприятном случае потребует
при количестве элементов в наборе 50000 пройти весь набор 2500000000 раз.
Может кто знает какой-нибудь алгоритм получения минимального неиспользуемого в наборе
значения? Подскажите что-нибудь по этому поводу
Ответы
Всего ответов: 9
Номер ответа: 1
Автор ответа:
Pashenko
ICQ: 176176951
Вопросов: 14
Ответов: 655
Профиль | | #1
Добавлено: 19.11.03 10:03
Попробуй сначала отсортировать список.
Номер ответа: 2
Автор ответа:
cresta
Вопросов: 117
Ответов: 1538
Профиль | | #2
Добавлено: 19.11.03 12:53
Если отсортировать имеется ввиду выстроить по возрастанию, то это как-раз и есть собственно говоря, конечная задача т.к. потом пробежать отсортированный набор и проверить каждый номер на существование номер+1 дело недолгое.
Номер ответа: 3
Автор ответа:
Pashenko
ICQ: 176176951
Вопросов: 14
Ответов: 655
Профиль | | #3
Добавлено: 19.11.03 13:22
Существует метод быстрой сортировки, т. н. Quiсk Sort.
Сам не реализовывал, но принцип такой:
1. Выбираем число в центре массива.
2. Последовательно сравниваем с ним все числа массива, если число,
стоящее выше, больше среднего, меняем их местами (для второй половины,
соответственно, наоборот). Таким образом получаем в первой половине
массива все числа меньше среднего, во второй половине - больше среднего.
3. Повторяем пп. 1, 2 для каждой половины массива (среднее число можно
исключить из рассмотрения), потом для каждой четверти и т. д. до упора.
Весь алгоритм, как правило выполняют в виде рекурсивной процедуры.
P. S. Насколько я знаю, более быстрого способа сортировки пока не
придумали.
Номер ответа: 4
Автор ответа:
cresta
Вопросов: 117
Ответов: 1538
Профиль | | #4
Добавлено: 19.11.03 15:40
Попробую, спасибо
Номер ответа: 5
Автор ответа:
Павел
Администратор
ICQ: 326066673
Вопросов: 368
Ответов: 5968
Web-сайт:
Профиль | | #5
Добавлено: 19.11.03 16:37
Гениально! Тогда ему нужно сортироват не весь массив, а после первого
прохода сортировать первую половину, потом первую четверть и т.д.
Получится намного быстрее!
А вообще, наверное, сущесвуют математические методы (я недавно походую
олимпиадную задачу видел).
Номер ответа: 6
Автор ответа:
Pashenko
ICQ: 176176951
Вопросов: 14
Ответов: 655
Профиль | | #6
Добавлено: 19.11.03 17:00
> нужно сортироват не весь массив, а после первого прохода сортировать
первую половину, потом первую четверть и т.д.
Вообще говоря, рекурсивный алгоритм подразумевает именно такой порядок
перебора.
Номер ответа: 7
Автор ответа:
cresta
Вопросов: 117
Ответов: 1538
Профиль | | #7
Добавлено: 19.11.03 18:17
положение т.к. кроме самого просмотра необходимо ещё и переставлять элементы набора,
что скорости не прибавляет никак
Короче состряпал такую функцию
Dim recCount As Integer, i As Integer, j As Integer
Dim Min As Double, FreeCode As Double
Dim arr() As Double
Adodc1.Recordset.MoveLast
recCount = Adodc1.Recordset.RecordCount
ReDim arr(recCount - 1) As Double ' определяем количество элементов в массиве
Adodc1.Recordset.MoveFirst
While Not Adodc1.Recordset.EOF 'заполнение массива кодами
arr(Adodc1.Recordset.AbsolutePosition - 1) = CDbl(Adodc1.Recordset.Fields(0).Value)
Adodc1.Recordset.MoveNext
Wend
Adodc1.Recordset.MoveFirst
FreeCode = 0 'поиск свободного кода начиная с 1
lbl_reSearch:
For i = 0 To recCount - 1 'просмотр массива на присутствие кода FreeCode +1
If FreeCode + 1 = arr(i) Then ' если искомый код существует,
FreeCode = arr(i) ' запоминаем его
GoTo lbl_reSearch' ищем следующий
End If
Next i
FreeCode = FreeCode + 1
findFreeCode = PadToString(Trim$(Str(FreeCode)), 12)
End Function
в 10 раз, но за каждый проход проверяется 10 значений):
If FreeCode + 1 = arr(i) Then ' если искомый код существует,
FreeCode = arr(i) ' запоминаем его
GoTo lbl_reSearch' ищем следующий
End If
If FreeCode + 2 = arr(i) Then ' если искомый код существует,
FreeCode = arr(i) ' запоминаем его
GoTo lbl_reSearch' ищем следующий
End If
...
...
If FreeCode + 10 = arr(i) Then ' если искомый код существует,
FreeCode = arr(i) ' запоминаем его
GoTo lbl_reSearch' ищем следующий
End If
Next i
Номер ответа: 8
Автор ответа:
Павел
Администратор
ICQ: 326066673
Вопросов: 368
Ответов: 5968
Web-сайт:
Профиль | | #8
Добавлено: 26.11.03 08:48
Тут мне такое письмо пришло:
---------
если можете, то добавьте в http://vbnet.ru/forum/show.asp?id=27174 такой
ответ
почему-то у меня не получилось
я думаю автору надо было уточнить вопрос
Как можно быстро определить минимальное свободное значение,
не встречающееся в наборе, но больше минимального встречающегося ?
Задача решается за три сканирования:
1.ищем минимальное число в массиве
2.заполняем еще один массив отметками о числах не больших
(минимальное+количество чисел)
3.ищем в этом массиве отсутствие отметки
вот пример
Public Function funPoiskNovogoChisla() As Currency
'подготовительная работа - создадим массив и заполним его
Dim Kolvo As Long 'количество чисел в массиве
Kolvo = 100000 'пусть будет, например, 100 тысяч
Dim Massiv() As Currency 'объявляем массив
ReDim Massiv(Kolvo) 'UBound массива устанавливаем равным Kolvo
Dim i As Long, x1 As Currency, x2 As Currency 'вспомогательные переменные
For i = 1 To UBound(Massiv) 'заполним массив случайными числами
Randomize
x1 = Int(1000000 * Rnd)
Randomize
x2 = Int(1000000 * Rnd)
Massiv(i) = x1 * 1000000 + x2
Next i
'переходим к решению задачи - поиску минимального свободного значения,
'не встречающееся в наборе
'сначала найдем наименьшее число в массиве
Dim MinChislo As Currency 'наименьшее число в массиве
MinChislo = Massiv(1) 'пусть будет равно первому числу в массиве
For i = 2 To UBound(Massiv)
If MinChislo > Massiv(i) Then MinChislo = Massiv(i)
Next i
Dim NovChislo As Currency 'число которое надо найти
Dim NovMassiv() As Boolean 'создадим еще один массив
ReDim NovMassiv(Kolvo + 1) 'UBound нового массива устанавливаем равным
(Kolvo+1)
For i = 1 To UBound(Massiv) 'просканируем исходный массив
If Massiv(i) - MinChislo <= UBound(Massiv) Then 'если число не больше
минимального
'на количество чисел в
массиве
NovMassiv(Massiv(i) - MinChislo + 1) = True 'то в новом массиве
отметим
End If 'что такое число есть
Next i
For i = 1 To UBound(NovMassiv) 'просканируем новый массив
If NovMassiv(i) = False Then 'незанятое место!
NovChislo = MinChislo + i - 1 'вот и новое число
Exit For 'выходим из сканирования
End If
Next i
funPoiskNovogoChisla = NovChislo
End Function
---------
Номер ответа: 9
Автор ответа:
cresta
Вопросов: 117
Ответов: 1538
Профиль | | #9
Добавлено: 26.11.03 13:04
Dim i As Long
Dim varDataRows As Variant
RS.Sort = "Code" 'сортировка RS по полю "Код" RS.MoveLast
recCount = RS.RecordCount
RS.MoveFirst
varDataRows = RS.GetRows(recCount) ' делаем снимок со всего рекордсета сразу For i = 1 To recCount
If i < CDbl(varDataRows(0, i - 1)) Then 'если условие верно, значит есть пропущеное в наборе кодов
'обозначаем пропущеное как свободный номер
End If
Next i
End Function