2 / 2 / 1
Регистрация: 23.11.2011
Сообщений: 87
1

Простой аналог MAP

08.04.2013, 22:42. Показов 2795. Ответов 3
Метки нет (Все метки)

Доброго времени суток,

Есть задание реализовать регистр граждан. В нем хранятся значения: идентификатор, имя, фамилия, адрес, время записи. Идентификатор уникальный для каждого. Суть задачи в том чтобы сэкономить максимум процессорного времени и памяти. Поэтому если гражданин изменил адрес не надо создавать новую запись, сохранить только измененные значения. Нельзя пользоваться stl втч и std::string, я вижу решение задачи так: класс который реализует простейший стринг с перегрузкой базовых операторов. Простейший map в виде ассоциативного массива число-строка с сортировкой по строке. Класс "гражданин", в котором есть ид, имя, фамилия, адрес, дата(тоже строка) последнего изменения. ИД инт, имя, фамилия, адрес, дата - массивы интов, в них, в порядке вложения, хранятся числа, соответсвующие строке из списка типа map. В основном классе программы хранится массив типа класс "гражданин", причем сортировка там идет по имени и фамилии с приоритетом на имя, (хранятся соотв. числа из списка map, а не сами строки). Каждая запись вкладывается в отсортированый массив так, чтобы не нарушить порядок. Для поиска Вани Петрова ищутся номера строк Ваня и Петров, потом бинарным поиском по этим двум ключам идет поиск в овсновном классе.

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

Спасибо.

Добавлено через 6 минут
С одной стороны, я выигрываю в памяти, так как все строковые данные гарантированно уникальные (на 10 000 граждан может оказаться только 500 уникальных фамилий, например), что экономит память, но сдругой строны надо бегать по ссылкам туда сюда, что не лучшим образом сказывается на скорости, несмотря на применение бинарного поиска.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
1
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
08.04.2013, 22:42
Ответы с готовыми решениями:

аналог класса map
есть ли у кого-нибудь примеры?или намеки с чего начать?

Реализовать собственный аналог контейнера std::map
Нужно реализовать собственный контейнер map. Подскажите как это вообще сделать, ибо совсем не...

Есть ли аналог Map <String,String> чтобы передавать его как указатель на данные?
Добрый день, подскажите, есть ли аналог Map &lt;String,String&gt; чтобы передавать его как указатель на...

Аналог Map и Multimap
Есть hashtable и namevaluecollection - это коллекции на хеше, первый - уникальные ключи, второй...

3
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
09.04.2013, 15:44 2
awpe, В лучшем случае: Поиск места для нового юзера, проверка существования юзера - log(n). Лучше всего реализовывать в виде красно-чёрного дерева, т.е. переписать set. И, кстати, map - отображение. Set - множество. Зачем вам целое отображение, когда вы хотите ускорить работу алгоритма ? В данной задаче оно не требуется. От уникальности можно избавиться (multiset). (PS Дерево должно строится на рекурсивной структуре, а не хранится в массиве, по многим причинам).
0
2 / 2 / 1
Регистрация: 23.11.2011
Сообщений: 87
09.04.2013, 18:23  [ТС] 3
Ternsip, вы немогли бы подробнее описать, как использовать предложенную вами структуру данных, для экономии места?

У меня был такой ход мысли: в худшем случае надо было бы каждый раз создавать новую запись (при изменении места жительства например), потом собирать массив (при запросе) с записями по конкретному человеку (select * from `bd` where `id`='ID' - аналог sql) и в сортированном виде (по дате) выдавать данные.

Как улучшить? - Сделать класс для гражданина, в котором хранится его ИД, имя. фамилия и массив для всего остального (этот массив сортирован по дате). уже лучше - можно в основном классе иметь массив граждан с сортировкой по ИД (т.к. по условию задачи запросы на поиск проводятся по ИД исключительно), и использовать бинарный поиск для нахождения записи. Собственно такой скорости работы программы достаточно, но здесь появляется вопрос с памятью, что если 20000 человек имеют 2000 уникальных фамилий? Одна фамилия пусть в среднем будет 8 символов, вместо 16000 символов храним 160000 символов, и так по всем строковым данным... Как улучшить - сделать словари для строк описывающих разные типы (имя, фамилия, город, улица). Так как задача для учебы, и выполнятся будет один раз при проверке, можно опустить вопрос с очисткой словарей от неиспользуемых данных, т.е. данные в них только добавляются. Словарь представлен уникальной парой - ключ и значение. Теперь можно в классе гражданин хранить, только ключи (числа) для соответсвующих словарей. Но здесь снова возвращается проблема скорости - при запрсое на вывод надо будет искать данные по этим ключам, что делать - вместо ключа использовать указатель на строку в массиве словаря. И вроде все - можно успокоится, но при добавлении новой строки в словарь надо сохранить ее уникальность, а поиск с таком маасиве будет выполнятся за линейное время - нужен сортированный массив, но ведь при добавлении новой строки в центр массива, произойдет смещение указателей, значит нужно другое решение....

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

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

Как устроен mysql, что он может быстро находить ячейки в таблице для их чтения/удаления/добавления данных ?
0
670 / 198 / 29
Регистрация: 10.05.2012
Сообщений: 595
09.04.2013, 18:31 4
awpe, Всё чрезвычайно просто. Всегда смотрите с точки зрения создания алгоритма. Базы данных почти не имеют отношения к данной задаче. Действуйте следующим образом: 0) Оставьте бинарный поиск, т.к. он делается по монотонной функции или упорядоченному массиву и он предназначен, исключительно, для поиска 1) Создайте структуру, описывающую параметры юзера, каждый параметр -- ссылка на узел в соотв. деревьях 2) Создайте шаблонную структуру узла бинарного дерева, затем опишите класс работы с этим деревом : поиск элемента в дереве, вставка элемента в дерево, размер дерева, проверка на пустоту и так далее. 3) После того, как описали шаблон этого упорядоченного множества (set) вы должны создавать библиотеки имён, возраста и так далее на основе этого дерева, и в конце создадите дерево вашей структуры.

Добавлено через 6 минут
Ах, да... И не забудьте перегрузить операторы сравнения для ваших структур, чтобы их можно было упорядочить, т.к. бинарное дерево требует оператор сравнения.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.04.2013, 18:31
Помогаю со студенческими работами здесь

Есть ли аналог map в Си?
В C++ есть функция map. Есть ли аналог этой функции в C ?

Датчики - аналог простой кнопки
Товарищи, объясните существуют ли датчики ( что то вроде сенсоров нажатий ), которые могут при...

Написать простой аналог Акинатора
Разработать программу, угадывающую персонажей, задуманных пользователем. Алгоритм реализовать...

Пишу простой аналог диспетчера задач
Добрый день. Пишу простой аналог диспетчера задач но уже в начале возникло пару трудностей. 1....


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

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru