Каков наилучший способ моделирования неупорядоченного списка (т. Е. Набора)?

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

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

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

Какой стандартный способ сделать это на современных языках (PHP, Perl, Ruby, Python и т. Д.)?

11.12.2008 18:59:17
7 ОТВЕТОВ
РЕШЕНИЕ

В Python вы бы использовали setтип данных. А setносители , содержащие любую hashable объекта, поэтому если у вас есть собственный класс , вам нужно хранить в наборе и hashable поведения по умолчанию не подходит, вы можете реализовать , __hash__чтобы реализовать поведение , которое вы хотите.

1
11.12.2008 19:02:25

C # имеет универсальную коллекцию HashSet <T>.

public class EmailAddress  // probably needs to override GetHashCode()
{
   ...
}

var addresses = new HashSet<EmailAddress>();
1
11.12.2008 19:05:28

Большинство современных языков будут иметь некоторую форму структуры данных Set. В Java есть HashSet , который реализует интерфейс Set .

В PHP вы можете использовать массив для хранения ваших данных. Либо выполните поиск в массиве перед добавлением нового элемента, либо используйте array_unique для удаления дубликатов после вставки всех элементов.

1
11.12.2008 19:07:15

В качестве замены для непосредственного понимания машины:

  • Для небольших, дискретных и четко определенных диапазонов: используйте побитовый массив, чтобы указать наличие каждого возможного элемента (установлен для настоящего, не установлен для отсутствующего).
  • Используйте хеш-таблицу для всех остальных случаев.

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


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

0
11.12.2008 19:38:27

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

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

Это действительно зависит от того, как вы хотите получить доступ и использовать данные.

0
11.12.2008 20:12:26

Массив, как правило, является самым простым способом хранения данных без каких-либо других требований. Обычно другие типы данных используются по разным причинам (вы хотите добавить данные, вы хотите искать данные в постоянном времени, вам нужно быстро установить объединение / пересечение и т. Д.) Если вас беспокоит только абстракция, вы можете обернуть ее в какой-то вид неупорядоченный фасад.

0
11.12.2008 20:19:48

В Perl я бы определенно использовал хеш. На других языках я бы посетовал на отсутствие хэша.

0
11.12.2008 20:24:22
на каких других языках это будет?
Jimmy 11.12.2008 20:26:41
Любой язык, который не имеет хешей. :) Многие из них делают, в том числе все, что я мог бы использовать в настоящее время, например, Java.
skiphoppy 12.12.2008 17:07:52