Проверка наличия элемента во множестве

@klast · Регистрация: 19.01.2011

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

в Питоне есть такая штука как множества, и там, например, поиск во множестве элемента составляет O(1), что очень удобно
есть ли что-нить похожее в паскале?

@Darius · 28.08.2012, 05:15

Есть тип "Множество"

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
var
  a: set of '0'..'9';
 
begin
  a += ['1', '3', '5', '7', '9'];
  writeln(a);
  if '1' in a then 
    writeln('true');
    
  foreach s: char in a do
    write(s, ' ');
  
end.

@klast · 28.08.2012, 12:17 **[ТС]**

а за какое время он добавляет во множество и за какое время он ищет элемент там?

@volvo · 28.08.2012, 12:37

Работа со множествами - битовая операция. Все сводится к проверке определенного бита, поэтому O(1).

@Darius · 28.08.2012, 13:02

klast, Берешь к примеру set of integer, добавляешь 100000 элементов. Считаешь по таймеру за сколько времени выполнится, полученный результат делишь на 100000, вот тебе и время добавления одного элемента. То же самое можешь проделать и с поиском.

Простейший пример подсчета времени операции, но скорее всего увидишь одни нули, или пару милисекунд

@klast · 28.08.2012, 13:32 **[ТС]**

Сообщение от UI

Работа со множествами - битовая операция. Все сводится к проверке определенного бита, поэтому O(1).

добавление во множество, происходит на O(N)
надо в памяти создать новое место для элемента, а это происходит на O(N)

@volvo · 28.08.2012, 13:41

Это ты про питон рассказываешь? Может быть. В Паскале, когда ты описываешь тип множества, уже известно, сколько бит (и, соответственно, байт) надо для его представления, и в памяти под переменную выделяется нужное количество байт. Еще раз: это битовая операция. Добавление элемента во множество - это просто включение определенного бита. Выполняется за O(1).

(хотя, в Pascal ABC.NET может быть другая история, там от Паскаля-то ничего не осталось, только ключевые слова некоторые. Возможно, они и множества по-своему реализовали)

@Puporev · 28.08.2012, 14:24

В Pascal ABC.NET можно запустить почти любую простенькую программу, написанную в Турбо Паскале или в простом АВС.

@klast · 28.08.2012, 14:31 **[ТС]**

Еще один вопрос!
эти множества есть только в ПаскальАБЦ.НЕТ?

@Puporev · 28.08.2012, 14:33

klast, В любом Паскале и Делфи, другое не знаю.

@Darius · 28.08.2012, 14:33

TurboPascal PascalABC точно есть, на счет борланда не в курсе, не работал с ним, но думаю тоже есть

@klast · 28.08.2012, 14:44 **[ТС]**

хмм, у меня код работает на абц.нет, а на обычном не хочет

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
var
  s: string;
  i, j, res, n, l: longint;
  h: boolean;
  used: set of string;
 
begin
  readln(s);
  res := 0;
  n := length(s);
  for i := 1 to n do
    for j := i to n do
      for l := j to n do
        if (i <> j) and (j <> l) and (l <> i) then
        begin
          h := true;
          if s[i] + s[j] + s[l] in used then h := false;
          if (h) and (s[i] <> '0') then 
          begin
            inc(res);
            used :=  used + [s[i] + s[j] + s[l]];
          end;
        end;
  writeln(res);
end.

чо в нем не так?

@Puporev · 28.08.2012, 14:51

klast, В простом нет множества строк, только set of byte и set of char, а также множества на основе перечислимого типа.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@klast тыдыщ 206 / 189 / 166 Регистрация: 19.01.2011 Сообщений: 483

	Проверка наличия элемента во множестве 28.08.2012, 00:32. Показов 8480. Ответов 12 Метки нет (Все метки) в Питоне есть такая штука как множества, и там, например, поиск во множестве элемента составляет O(1), что очень удобно есть ли что-нить похожее в паскале? 0

@klast тыдыщ 206 / 189 / 166 Регистрация: 19.01.2011 Сообщений: 483
	28.08.2012, 12:17 [ТС]
	а за какое время он добавляет во множество и за какое время он ищет элемент там? 0

@volvo Супер-модератор 33398 / 21508 / 8236 Регистрация: 22.10.2011 Сообщений: 36,906 Записей в блоге: 12
	28.08.2012, 12:37
	Работа со множествами - битовая операция. Все сводится к проверке определенного бита, поэтому O(1). 1

@Darius 37 / 37 / 26 Регистрация: 31.05.2009 Сообщений: 103
	28.08.2012, 13:02
	klast, Берешь к примеру set of integer, добавляешь 100000 элементов. Считаешь по таймеру за сколько времени выполнится, полученный результат делишь на 100000, вот тебе и время добавления одного элемента. То же самое можешь проделать и с поиском. Простейший пример подсчета времени операции, но скорее всего увидишь одни нули, или пару милисекунд 1

@volvo Супер-модератор 33398 / 21508 / 8236 Регистрация: 22.10.2011 Сообщений: 36,906 Записей в блоге: 12
	28.08.2012, 13:41
	Это ты про питон рассказываешь? Может быть. В Паскале, когда ты описываешь тип множества, уже известно, сколько бит (и, соответственно, байт) надо для его представления, и в памяти под переменную выделяется нужное количество байт. Еще раз: это битовая операция. Добавление элемента во множество - это просто включение определенного бита. Выполняется за O(1). (хотя, в Pascal ABC.NET может быть другая история, там от Паскаля-то ничего не осталось, только ключевые слова некоторые. Возможно, они и множества по-своему реализовали) 1

@Puporev Почетный модератор 64315 / 47611 / 32743 Регистрация: 18.05.2008 Сообщений: 115,167
	28.08.2012, 14:24
	В Pascal ABC.NET можно запустить почти любую простенькую программу, написанную в Турбо Паскале или в простом АВС. 0

@klast тыдыщ 206 / 189 / 166 Регистрация: 19.01.2011 Сообщений: 483
	28.08.2012, 14:31 [ТС]
	Еще один вопрос! эти множества есть только в ПаскальАБЦ.НЕТ? 0

@Puporev Почетный модератор 64315 / 47611 / 32743 Регистрация: 18.05.2008 Сообщений: 115,167
	28.08.2012, 14:33
	klast, В любом Паскале и Делфи, другое не знаю. 1

@Puporev Почетный модератор 64315 / 47611 / 32743 Регистрация: 18.05.2008 Сообщений: 115,167
	28.08.2012, 14:51
	klast, В простом нет множества строк, только set of byte и set of char, а также множества на основе перечислимого типа. 1