Ндааааа....

← →
vuk © (2009-01-21 21:15) [0]

program Project1;
{$APPTYPE CONSOLE}

uses
SysUtils,
Generics.Collections;

var
list: TList<integer>;
i, index:integer;
begin
list := TList<integer>.Create;
try
for i := 0 to 10 do
list.Add(i);
for i := 0 to 10 do
begin
if not list.BinarySearch(i, index) then
index := -1;
writeln(format("Value: %d; index: %d", [i, index]));
end;
finally
list.Free;
end;
readln;
end.
-------------------------
Результат:

Value: 0; index: 0
Value: 1; index: -1
Value: 2; index: 0
Value: 3; index: -1
Value: 4; index: -1
Value: 5; index: 0
Value: 6; index: -1
Value: 7; index: -1
Value: 8; index: -1
Value: 9; index: -1
Value: 10; index: -1

← →
Jeer © (2009-01-21 22:08) [1]

Да уж.. как бы сказать поаккуратнее.. :)

Сколько лет писаю на того или иного вида "бамагу" - ну, еж твою - не возникает
какого-либо видоизменений лакмусовой "бамаги".
Ну, что я делаю не так ?
Объясните, в конце-то концов !
Не, не о том "конце" речь - с тем концом усе упорядке :)

← →
Petr V. Abramov © (2009-01-21 22:14) [2]

> Объясните, в конце-то концов !
> Не, не о том "конце" речь - с тем концом усе упорядке :)

да, у меня все порядке.
Не, не о том "конце" речь - с тем концом усе упорядке :)

← →
vuk © (2009-01-21 22:25) [3]

Что-то непонятно?
Delphi 2009, win32, дженерики, поиск половинным делением не работает. Напрочь.

← →
ketmar © (2009-01-21 22:35) [4]

а шо это вы тут делаете? O_O

---
Do what thou wilt shall be the whole of the Law.

← →
palva © (2009-01-21 22:46) [5]

> дженерики, поиск половинным делением не работает. Напрочь.

А может надо как-то сообщить этому списку, что он отсортирован? Данные, правда, по факту отсортированы... Но я бы поискал какое нибудь .sorted := true

← →
KilkennyCat © (2009-01-21 22:50) [6]

> vuk ©

Генофонд не копал?

← →
vuk © (2009-01-21 23:02) [7]

Список в данном случае отсортирован изначально, так что вызов сортировки ничего не даст. В генофонд заглянул. Ошибка именно там. Что за обезьяна писала BinarySearch я так и не понял. Но тестированием этого точно никто не занимался.

← →
KilkennyCat © (2009-01-21 23:08) [8]

Странно, зачем его вообще трогали. И как его могли испортить? Это ж классика... Сегодня полюбопытствую, как машину восстановлю.

← →
Сергей М. © (2009-01-21 23:13) [9]

> vuk © (21.01.09 23:02) [7]

А можно ли глянуть на генообезьянокод этого самого BinariSearch ?

← →
vuk © (2009-01-21 23:16) [10]

Вот мне тоже это непонятно. Как можно было наколбасить то, что там написано, если даже тупое передирание из любого места, где такой поиск есть, деёт нормальный результат? В институте за такое двойки ставят.

← →
KilkennyCat © (2009-01-21 23:27) [11]

Страшно то, что теперь нельзя будет доверять ни чему...

← →
vuk © (2009-01-21 23:50) [12]

class function TArray.BinarySearch<T>(const Values: array of T; const Item: T; out FoundIndex: Integer; const Comparer: IComparer<T>; Index, Count: Integer): Boolean; var L, H: Integer; mid, cmp: Integer; begin if (Index < Low(Values)) or (Index > High(Values)) or (Index + Count - 1 > High(Values)) or (Count < 0) or (Index + Count < 0) then raise EArgumentOutOfRangeException.CreateRes(@sArgumentOutOfRange); if Count = 0 then begin FoundIndex := 0; Exit(False); end; L := Index; H := Index + Count - 1; while L <= H do begin mid := L + (H - L) shr 1; cmp := Comparer.Compare(Values[mid], Item); if cmp < 0 then L := mid + 1 else if cmp = 0 then begin FoundIndex := L; Exit(True); end; H := mid - 1; end; FoundIndex := L; Result := False; end;

← →
jack128_ (2009-01-21 23:56) [13]

Удалено модератором

← →
jack128_ (2009-01-21 23:58) [14]

это я к тому, что щупать дженерики и анонимные методы можно будет тока в d2010 и то если очень повезет.

← →
vuk © (2009-01-22 01:14) [15]

Собственно да, компилятор на дженериках пока того... Смотрю в QC... Жесть... В принципе, примерно это и ожидалось... :(

← →
Германн © (2009-01-22 01:21) [16]

> KilkennyCat © (21.01.09 23:27) [11]
>
> Страшно то, что теперь нельзя будет доверять ни чему...
>

А уже давно нельзя доверять ничему и никому! Первым меня подвёл Atmel. И до сих пор я не смог решить эту задачу. :(

← →
Eraser © (2009-01-22 01:23) [17]

> [15] vuk © (22.01.09 01:14)

> Смотрю в QC... Жесть... В принципе, примерно это и ожидалось...

беда даже не в том, что там багов много, а в том, что они их не правят. выпускают обновления, где не исправлены все известные баги, что вкорне не правильно.

← →
KilkennyCat © (2009-01-22 01:48) [18]

> Германн ©

Я тебе предлагал помощь. Предлагаю и сейчас, ибо полностью в Атмелах сейчас.

← →
Германн © (2009-01-22 01:52) [19]

> KilkennyCat © (22.01.09 01:48) [18]
>
>
> > Германн ©
>
> Я тебе предлагал помощь. Предлагаю и сейчас, ибо полностью
> в Атмелах сейчас.
>

Я помню. Почта в анкете рабочая? Если да, то спрошу завтра.

← →
test (2009-01-22 05:25) [20]

А в какой версии появились типизированные TList?

← →
KilkennyCat © (2009-01-22 09:20) [21]

> Германн © (22.01.09 01:52) [19]

в анкете не помню, здесь - да.

← →
Sha © (2009-01-22 11:18) [22]

На первый взгляд в [12] нет ошибки.

← →
Sha © (2009-01-22 11:37) [23]

нашел )
FoundIndex := L;

← →
Marser © (2009-01-22 11:37) [24]

Это дженерики тут только сейчас появились или я что-то важное раньше пропустил?

← →
vuk © (2009-01-22 11:43) [25]

to Sha © (22.01.09 11:18) [22]:
>На первый взгляд в [12] нет ошибки.
Ага. Ну да, похоже. Только вот на второй, а особенно после трассировки, становится видна вся белиберда. Для начала обратите внимание, что именно функция возвращает в качестве результата, когда cmp = 0.

Вот, для осознания разницы, вариант из QC, который предложил Rudy Velthuis:

class function TArray.BinarySearch<T>(const Values: array of T; const Item: T; out FoundIndex: Integer; const Comparer: IComparer<T>; Index, Count: Integer): Boolean; var L, H: Integer; mid, cmp: Integer; begin if (Index < Low(Values)) or (Index > High(Values)) or (Index + Count - 1 > High(Values)) or (Count < 0) or (Index + Count < 0) then raise EArgumentOutOfRangeException.CreateRes(@sArgumentOutOfRange); if Count = 0 then begin FoundIndex := 0; Exit(False); end; Result := False; L := Index; H := Index + Count - 1; while L <= H do begin mid := L + (H - L) shr 1; cmp := Comparer.Compare(Values[mid], Item); if cmp < 0 then // mods 09/29/2008 R. Velthuis L := mid + 1 else begin H := mid - 1; if cmp = 0 then Result := True; end; end; FoundIndex := L; end;

Или вот еще:
function TStringList.Find(const S: string; var Index: Integer): Boolean; var L, H, I, C: Integer; begin Result := False; L := 0; H := FCount - 1; while L <= H do begin I := (L + H) shr 1; C := CompareStrings(FList^[I].FString, S); if C < 0 then L := I + 1 else begin H := I - 1; if C = 0 then begin Result := True; if Duplicates <> dupAccept then L := I; end; end; end; Index := L; end;

← →
Добежал (2009-01-22 11:44) [26]

> list: TList<integer>;

а что это такое за определение <integer>?!?!

← →
Sha © (2009-01-22 11:51) [27]

vuk © (22.01.09 11:43) [25]

думаю, там у них просто ошибка при копи-паст вкралась (см. [23])

достаточно первый FoundIndex := L;
заменить на FoundIndex := mid;

← →
vuk © (2009-01-22 11:54) [28]

to Marser © (22.01.09 11:37) [24] :
>Это дженерики тут только сейчас появились или я
>что-то важное раньше пропустил?
В D2009 они появились. Но, судя по QC, всё это пока неюзабельно. Помимо того, что в самой библиотеке такие вот ляпы, так еще и компиятор фигню гонит.

to Добежал (22.01.09 11:44) [26]:
> list: TList<integer>;
а что это такое за определение <integer>?!?!
integer - это тип данных такой. :) А TList<integer> - это объявление строго типизированного списка для элементов типа integer.

Т.е. дело скорее всего было так:
сначала забыли возвращать FoundIndex в случае успеха,
затем в процессе отладки это обнаружили и скопипастили присвоение,
которое было в случае неуспеха.

to Sha © (22.01.09 11:51) [27]:
>думаю, там у них просто ошибка при копи-паст вкралась (см. [23])
Да нет, это не копи-паст. Это человек решил цикл соптимизировать. Ну и "соптимизировал" - посмотрел, что за пределами цикла возвращается в качестве найденного индекса, прописал это в FoundIndex и свалил из функции. А то, что переменная еще в пределах цикла меняется, если не свалить, то это как-то от него ускользнуло. А на тестирование вообще забил.

>[30] vuk © (2009-01-22 11:59:00)
потому что кодожир — страшное, неописуемое, ненужное говно. как и все дельфя после D7, увы.

---
All Your Base Are Belong to Us

to ketmar © (22.01.09 12:16) [31]:
>потому что кодожир — страшное, неописуемое, ненужное говно.
>как и все дельфя после D7, увы.

Ну, надо сказать, что D2009 на больших проектах стабильнее и D7 и D6...

> достаточно первый FoundIndex := L;
> заменить на FoundIndex := mid;

H := mid - 1;

>Да нет, это не копи-паст. Это человек решил цикл соптимизировать. Ну и "соптимизировал"

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

А ведь казалось бы - и идея очень проста, в нескольких словах можно объяснить, и реализация в несколько строчек - ан нет, на грабельки почти все наступают...

← →
Sergey Masloff (2009-01-22 14:19) [35]

MBo © (22.01.09 13:54) [34]
Это в Керниган-Пайк "Практика программирования", насколько я помню.
Ключевое слово - с первого раза. Видимо там сетак и пишут - что вижу то пише пользователи протестируют ;-)

Многие не только реализовать нормально не могут, но и передрать - не очень-то...

Да, ещё. Если даже вернуть mid и поставить H := mid - 1 туда, куда надо, то такая реализация не будет учитывать возможное наличие дубликатов. Так что нормальная реализация - та, что из QC.

Мужики, ну шо вы взъелись? Хлопцы по ночам код хреначили. Какие еще могу быть результаты. Но вот огорчило меня это. я так надеялся на дженерики, блин. задолбался уже TObjectList"ы городить кругом

Паш, их, конечно, юзать можно, но только осторожно очень. И, похоже, лучше свою реализацию классов наваять... Хотя, от глюков компилятора это не спасет.

← →
qqq (2009-01-22 17:08) [40]

> выпускают обновления, где не исправлены все известные баги,
> что вкорне не правильно.

пытаются побыстрее залепить особо зияющие дыры, а остальные потом, отдельно

кстати, где можно качнуть обновления, чтоб не просило код регистрации?

Ндааааа.... Найти похожие ветки