Форум программистов, компьютерный форум, киберфорум
Pascal (Паскаль)
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.69/13: Рейтинг темы: голосов - 13, средняя оценка - 4.69
6 / 5 / 1
Регистрация: 30.07.2014
Сообщений: 56

Возможно ли организовать бинарный поиск в двусвязном списке?

30.07.2014, 14:58. Показов 2713. Ответов 8
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Доброго времени суток.

Возможно ли на pascal организовать бинарный поиск в двусвязном списке?
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
30.07.2014, 14:58
Ответы с готовыми решениями:

Бинарный поиск в двусвязном списке
Кто-нибудь знает, как использовать бинарный поиск на двусвязных списках?

Бинарный поиск в двусвязном списке
Есть класс #ifndef STUDENT_H_INCLUDED #define STUDENT_H_INCLUDED #include <iostream> #include <string> #include <iterator> ...

Как организовать поиск в двусвязном списке?
Есть класс двусвязный список где каждый элемент имеет большое количество полей (Имя, Фамилия, Отчество, номер телефона, дата рождения ) ,...

8
Модератор
10448 / 5739 / 3407
Регистрация: 17.08.2012
Сообщений: 17,459
30.07.2014, 15:21
Конечно, по определению возможно организовать бинарный поиск в отсортированном двусвязном списке, в том числе и на языке pascal.
0
6 / 5 / 1
Регистрация: 30.07.2014
Сообщений: 56
31.07.2014, 09:44  [ТС]
Я предпологаю, что это возможно. Но как?

Задача такая. Нужно удалить из TString повторяющиеся строки. Самым быстрым алгоритмом мне кажется будет заполнение списка с сортировкой, т.е. если каждую строку помещать в список на свое место по возростанию поиск можно организовать по бинарному методу. Данных не мало, порядка 2 млн. строк. Реализация в TStringList не подходит, очень долго выполняется (около 10 мин.). Имеется ввиду:
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  procedure SetList(First, last: integer);
  var
    list: TStringList;
    i: integer;
  begin
    list := TStringList.Create;
    try
      list.Sorted := True;
      list.Duplicates := dupIgnore;
      for i := First to last do
        list.Add(Lines[i]); // происходит заполнение данных с сортировкой, дубликаты игнорируются
    finally
      list.Free;
    end;
  end;
Переписал с использованием массивов. Выдает примерно такое же время, но чуть быстрее. Код.
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
  procedure QuickSetList(First, last: integer);
  var
    dInt: array of integer; // хранятся индексы по возростанию списка list
 
    function Find(const str: string; out index: integer): boolean;
    var
      l, r, i: integer;
      CompareRes: PtrInt;
    begin
      Result := False;
      // используется бинарный поиск
      l := 0;
      r := dCnt - 1;
      while (l <= r) do
      begin
        i := l + (r - l) div 2;
        CompareRes := AnsiCompareStr(str, list[dInt[i]]);
        if (CompareRes > 0) then
          l := i + 1
        else
        begin
          r := i - 1;
          if (CompareRes = 0) then
          begin
            Result := True;
            l := i;
          end;
        end;
      end;
      index := l;
    end;
 
  var
    i, j, index: integer;
    curStr: string;
    list: TStringList;
  begin
    list := TStringList.Create;
    try
      SetLength(dInt, Lines.Count);
      try
        i := First;
        while i <= last do
        begin
          curStr := Lines[i];
          if (curStr = '') or not Find(curStr, index) then // если в списке не найден, то происходит вставка на свое место по возростанию. Дубликат игнорируется.
          begin
            Inc(dCnt);
            list.Add(curStr);
            j := dCnt - 1;
            while j > index do // все что ниже смещается на 1.
            begin
              dInt[j] := dInt[j - 1];
              Inc(j, -1);
            end;
            dInt[index] := dCnt - 1;
          end;
          Inc(i);
        end;
      finally
        Finalize(dInt);
      end;
    finally
      list.Free;
    end;
  end;
Возможно с указателями выполнится быстрее... Но не настолько, как в след. примере.

Реализация на c++ выдает 5 с. Да-да., этому коду 2 млн. строк расплюнуть.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <set>
 
struct scnt
{
        std::string m_s;
        mutable int m_c;
        scnt(const char* ch): m_s(ch), m_c(0) {};
        bool operator<(const scnt& rhs) const { return (m_s < rhs.m_s); };
};
 
typedef std::set<scnt> scntset;
typedef scntset::iterator scntseti;
typedef std::pair<scntseti, bool> scntsetp;
 
scntset myset;
 
int main()
{
        char* line = 0;
        size_t len = 0;
 
        scntsetp p;
        int nblines = 0;
 
        while ((getline(&line, &len, stdin)) != -1)
        {
                ++nblines;
                scnt t(line);
 
                p = myset.insert(t);
                if (p.second == false) // already exists
                {
                        p.first->m_c+=1;
                }
        }
 
        printf("%d elements, %d uniques\n", nblines, myset.size());
        free(line);
        return 0;
}
Результат.
Bash
1
2
3
4
mccp% cat testF.txt | /usr/bin/time ./a.out
2185876 elements, 2185876 uniques
4.57user 0.70system 0:05.59elapsed 94%CPU (0avgtext+0avgdata 1343424maxresident)k
0inputs+0outputs (0major+84007minor)pagefaults 0swaps
Как можно добится такого результата на языке pascal (ну или delphi)? Хотябы примерно.
0
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
 Аватар для volvo
33402 / 21512 / 8236
Регистрация: 22.10.2011
Сообщений: 36,911
Записей в блоге: 12
31.07.2014, 11:47
ardans,
Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
procedure SetList2(First, last: integer);
var
  L, list: TStringList;
  i: integer;
begin
  L := TStringList.Create;
  for i := First to last do
    L.Add(Lines[i]);
  L.Sort;
 
  list := TStringList.Create;
  try
    list.Sorted := True;
    list.Duplicates := dupIgnore;
    list.Assign(L);
  finally
    list.Free;
  end;
 
  L.Free;
end;
, на 200-тысячном интервале более чем 15-кратный выигрыш по скорости по сравнению с твоим первым кодом. На миллионах будет еще больше... Сам догадаешься, почему?
1
6 / 5 / 1
Регистрация: 30.07.2014
Сообщений: 56
31.07.2014, 14:24  [ТС]
Да, так быстрее. Даже правильнее и быстрее использовать вместо
Pascal
1
2
3
4
5
6
7
8
9
  list := TStringList.Create;
  try
    list.Sorted := True;
    list.Duplicates := dupIgnore;
    list.Assign(L);
  finally
    list.Free;
  end;
выполняется 4:51
использовать (раз он отсортирован)
Pascal
1
2
3
4
5
          for i := First+1 to last do
          begin
            if L[i] = L[i-1] then ;
          end;
выполняется 2:55
Но в таком случае теряется связь с Lines. А связь нужна для удаления дубликата в Lines. Да и все равно, с кодом на c++ по быстроте не сравнится.
0
Супер-модератор
Эксперт Pascal/DelphiАвтор FAQ
 Аватар для volvo
33402 / 21512 / 8236
Регистрация: 22.10.2011
Сообщений: 36,911
Записей в блоге: 12
31.07.2014, 15:17
Лучший ответ Сообщение было отмечено ardans как решение

Решение

Цитата Сообщение от ardans Посмотреть сообщение
Но в таком случае теряется связь с Lines.
Никто не запрещал очистить Lines и занести в него содержимое List. Не придумывай себе проблемы...
Цитата Сообщение от ardans Посмотреть сообщение
Да и все равно, с кодом на c++ по быстроте не сравнится.
Не смеши меня...

Delphi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
uses System.Generics.Collections; // Delphi 2009 и выше
 
procedure SetList3(First, last: integer);
var
  list: TStringList;
  D : TDictionary<string, integer>;
  i: integer;
  k : string;
begin
  D := TDictionary<string, integer>.create;
  for i := First to last do
    D.AddOrSetValue(Lines[i], 0);
 
  list := TStringList.Create;
  try
    for K in D.Keys do
    List.Add(K); // можешь сразу в свой Lines заносить
    // можешь отсюда затолкать в lines
  finally
    list.Free;
  end;
  D.Free;
end;
убивает дубликаты из списка (интервал - 2 миллиона элементов) чуть больше чем за секунду. С++ твой хвалёный мурыжился 3.5 секунды...
5
 Аватар для Новичок
1682 / 1098 / 489
Регистрация: 17.07.2012
Сообщений: 5,361
31.07.2014, 19:50
Цитата Сообщение от UI Посмотреть сообщение
С++ твой хвалёный мурыжился 3.5 секунды...
Ахахах! Круто! Обломали! Интересно за счет чего такая скорость в Delphi?
0
31.07.2014, 21:05

Не по теме:

Новичок, что, правда, что ль, обломался? Ну эффективнее всю жизнь паскалевские компиляторы против сишных были в плане обработки структур данных с переменной длиной... Что ж поделаешь, си писался под машины DEC PDP-11, а работать вынужден на IBM PC... А паскаль, увы, ни подо что не писался...

Цитата Сообщение от Новичок Посмотреть сообщение
Интересно за счет чего такая скорость в Delphi?
Зачем спрашиваете? Возьмите оба экзешника, дизассемблируйте, да и посмотрите, какого рожна дельфи быстрее... Чем хвалёный С++.

0
6 / 5 / 1
Регистрация: 30.07.2014
Сообщений: 56
01.08.2014, 09:07  [ТС]
UI
Вот это другое дело. То что нужно. Спасибо!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
01.08.2014, 09:07
Помогаю со студенческими работами здесь

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

Поиск в двусвязном списке
#include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;cstring&gt; #include &lt;windows.h&gt; using namespace std; struct element{ ...

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

Поиск элемента в двусвязном списке
Подскажите пожалуйста. Нужно пройти по списку и найти слово по первой букве, запомнить адрес, и начиная от этого адреса пройтись влево и...

Поиск элемента в двусвязном списке
Элемент двусвязного списка точка(x,y). Нужно написать функцию для нахождения максимально удаленной точки от центра координат. ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Новые блоги и статьи
Автозаполнение реквизита при выборе элемента справочника
Maks 27.03.2026
Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .
Сумматор с применением элементов трёх состояний.
Hrethgir 26.03.2026
Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа
Maks 26.03.2026
Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .
Команды формы и диалоговое окно
Maks 26.03.2026
1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT?
DevAlt 26.03.2026
Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .
Отправка уведомления на почту при создании или изменении элементов справочника
Maks 24.03.2026
Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .
модель ЗдравоСохранения 5. Меньше увольнений- больше дохода!
anaschu 24.03.2026
Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .
Midnight Chicago Blues
kumehtar 24.03.2026
Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru