Модераторы: Poseidon

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Реализация объекта-таблицы через хеш-функцию. 
:(
    Опции темы
Chpok-Chpok
Дата 4.4.2005, 14:00 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 13
Регистрация: 29.3.2005

Репутация: нет
Всего: нет



И так теперь условие задачи в том варианте, который мы придумали вместе преподом smile :
Язык - Delphi.(Delphi 7).
Задача :
Разработать объект-таблицу, обеспечивающую обработку данных о складе следующего формата : организация, фамилия ответственного лица, площадь, занимаемая организацией, список товаров (дата поступления, наименование, количество).Каждая организация - строка таблицы.Объект должен содержать следующие методы :
1.Создание информации о всем складе в файле(я так понял запись всей информации в файл).
2.Формирование списков по организациям без указания остальной информации.
3.Формирование списка на каждую дату о количестве занятых метров и свободных площадях.
4.Исправление данных : удаление огранизации, исправление данных при вывозе товара, исправление данных при ввозе товара.
5.Все пункты должны сопровождаться выводом иныормации в специальное окно наблюдения за движением товара.

Теперь дополнение smile -
1.товаров у одной фирмы может быть несколько
2.площадь которую занимает фирма не зависит от количества товаров, имеющихся у данной фирмы
3.Теперь самое главное - моя задача оказывается предполагает решение через список списков smile

Мои небольшие просьбы :
1.Напишите пожалуйста процедуру добавления элемента таблицу.
2.Удаления элемента из таблицы.

С остальным я разберусь и напишу сам. Заранее спасибо.
PM MAIL   Вверх
maxim1000
Дата 4.4.2005, 14:33 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

Репутация: 24
Всего: 110



Цитата
Просто говоря хэш функция считает циклическую сумму данных:
аббв = номер(а)*1+номер(б)*2+номер(б)*4+номер(в)*8
при других перестановках букв, значение будет другое. Используется для быстрого поиска.
Часто требуется на олимпиадах.


хеш функция значительно более часто используется в организации данных таким образом, чтобы было легче искать (не будем вспоминать про криптографию - там отдельный разговор) smile
пример:
есть несколько организаций, у каждой свой номер (выбирается случайно)
все они хранятся в массиве
время от времени их нудно добавлять, время от времени их нужно там находить
есть такой вариант:
1. хранить весь массив упорядочено
2. поиск проводить бисекцией (время пропорционально логарифму количества записей)
это, конечно, хорошо, но при добавлении нужно "досортировывать" массив, что требует времени, пропорционально количеству записей

есть другой вариант - использовать хеш-функции
самый тривиальный вариант:
1. берем количество букв в названии организации и используем это для деления организаций на две группы (четное/нечетное)
2. делаем два массива (будем хранить их упорядочено)
3. при поиске ничего не изменилось (сначала надо определить, в каком массиве искать, потом найти)
4. а вот при добавлении записи заметны улучшения: считаем количество букв в названии, берем соответствующий массив и заносим объект туда, т.к. элементов там будет в среднем половина, то и операций на пересортировку нами будет затрачено в два раза меньше

так хеш, конечно, не стоит использовать (в смысле деление на два массива), это - для понимания
но принцип остается тот же
вот пример, который приводил преподаватель:
1. придумываем функцию от объекта, чтобы давала целое число 1..M
2. создаем массив из N указателей, каждый указатель указывает на массив или список
3. при добавлении объекта вычисляем функцию, берем соответствующий массив, добавляем в него
4. при поиске - то же самое

если функция хорошая, то в каждом подмассиве будет приблизительно N/M элементов, что значительно уменьшает время на операции (особенно, если M большое)

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


--------------------
qqq
PM WWW   Вверх
Chpok-Chpok
Дата 4.4.2005, 19:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 13
Регистрация: 29.3.2005

Репутация: нет
Всего: нет



И так забыли про хеш-функцию.Вопрос на повестке дня - реализация двух методов вышеописанных мною.
PM MAIL   Вверх
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman

 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »


 




[ Время генерации скрипта: 0.0649 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.