Форум программистов, компьютерный форум CyberForum.ru

Простой аналог MAP - C++

Восстановить пароль Регистрация
 
awpe
2 / 2 / 0
Регистрация: 23.11.2011
Сообщений: 87
08.04.2013, 22:42     Простой аналог MAP #1
Доброго времени суток,

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

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

Спасибо.

Добавлено через 6 минут
С одной стороны, я выигрываю в памяти, так как все строковые данные гарантированно уникальные (на 10 000 граждан может оказаться только 500 уникальных фамилий, например), что экономит память, но сдругой строны надо бегать по ссылкам туда сюда, что не лучшим образом сказывается на скорости, несмотря на применение бинарного поиска.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.04.2013, 22:42     Простой аналог MAP
Посмотрите здесь:

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

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

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

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

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

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

Добавлено через 6 минут
Ах, да... И не забудьте перегрузить операторы сравнения для ваших структур, чтобы их можно было упорядочить, т.к. бинарное дерево требует оператор сравнения.
Yandex
Объявления
09.04.2013, 18:31     Простой аналог MAP
Ответ Создать тему
Опции темы

Текущее время: 13:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru