Интересные интересности и задачи/головоломки

[Аватар]

Так это и будет, пусть и усовершенствованный, но один из самых не эффективных видов поиска. Почему выше и были дебаты по поводу бинарного поиска и двоичных деревьев

[Sibedir]

Сообщение от Аватар

... это и будет ... но один из самых не эффективных видов поиска.

Обоснуй
Если есть другой "эффективных" способ, то уж точно не деревья. Ну не в этом случае.

[Poma][a]

Потому что сложность будет квадратичная

А деревья:почему они Вам не нравятся? В данном случае они позволяют найти наш элемент (или создать его) за логарифм

[Sibedir]

Сообщение от Poma][a

Потому что сложность будет квадратичная

А деревья:почему они Вам не нравятся? В данном случае они позволяют найти наш элемент (или создать его) за логарифм

Деревья памяти сожрут больше (Или я чёта не понял).

А вообще, чем проще тем проще:

const
  _FILMCOUNT = 10;

type
  TFilmItem = record
    Name: AnsiString;
    Count: Integer;
  end;

  TFilmArr = array of TFilmItem;

procedure Sort (var aFA: TFilmArr);
begin
  // ...
end;

...

procedure TForm1.Button2Click(Sender: TObject);
var
  c: Cardinal;
  TF: TextFile;
  i, j, n: Integer;
  FilmArr: TFilmArr;
  s: AnsiString;
  cur, count: Integer;
begin
  c := GetTickCount;

  AssignFile (TF, ExtractFilePath(ParamStr(0)) + 'input.txt');
  Reset(TF);


  count := 0;
  SetLength (FilmArr, _FILMCOUNT);
  for i := 0 to _FILMCOUNT-1 do begin
    FilmArr[i].Name := '';
    FilmArr[i].Count := 0;
  end;

  Readln (TF, n);

  for i := 1 to n do begin
    Readln (TF, s);

//    Continue;

    cur := 0;
    for j := 0 to count-1 do begin
      if FilmArr[j].Name = s then
        Break
      else
        Inc (cur)
    end;

    if FilmArr[cur].Count = 0 then begin
      FilmArr[cur].Name := s;
      Inc (count)
    end;
    Inc (FilmArr[cur].Count);
  end;

  Sort (FilmArr);

  ListBox1.Items.Clear;
  for i := 0 to count-1 do begin
    s := FilmArr[i].Name + ' ' + IntToStr (FilmArr[i].Count);
    ListBox1.Items.Add (s)
  end;

  SetLength (FilmArr, 0);
  CloseFile(TF);

  Button2.Caption := IntToStr (GetTickCount - c);
end;

Опуская нюансы чтения/записи и сортировки - работает почти мгновенно. Памяти ~минимум.

[Poma][a]

Хех, при 10 оно так и будет. А при 1000 уже будете успевать моргнуть 2 раза. При 10000 сможете выпить кофе

А память.. Если ее хорошо выделять, то не сильного много и выйдет. Не будет намного больше массива

[Аватар]

Sibedir

Просто поиск простым перебором в массиве [1..10] в среднем ~5 сравнений, бинарный ~ 2.5. И тогда время на сотне миллионов поисков будет заметно. Пусть и не часы и даже не минуты. А массив или дерево в данном случае без разницы, даже массив будет чуть лучше

[Sibedir]

Сообщение от Poma][a

Хех, при 10 оно так и будет. А при 1000 уже будете успевать моргнуть 2 раза. При 10000 сможете выпить кофе

Не, ну если до нельзя усложнять задачу...

А память.. Если ее хорошо выделять, то не сильного много и выйдет. Не будет намного больше массива

Мне кажется не выйдет ни чего с деревом. Если дерево по размеру будет как массив, то оно же не сможет обеспечить большую скорость работы. Я так понимаю: или избыточность памяти или операций.
Хотя операции тоже можно сократить. В моём примере избыточным является, конечно же:

FilmArr[j].Name = s

[Poma][a]

Если строить дерево, как список, то все получится. Да, будут ещё указатели на детей, но это не сильно много

[Sibedir]

Сообщение от Poma][a

Если строить дерево, как список, то все получится. Да, будут ещё указатели на детей, но это не сильно много

Не сильно много - это сколько?

[Poma][a]

А посчитайте.. Два сына каждый по 2 байта. Если всего фильмов N.. 2*N байт лишних

А про бинарный поиск : у нас же вставка будет.. Не ахти