Важная информация
Страница 1 из 5 123 ... ПоследняяПоследняя
Показано с 1 по 10 из 45

Тема: Что-то типа словаря (Map)

  1. #1 Что-то типа словаря (Map) 
    Профи Аватар для stabud
    Регистрация
    05.01.2013
    Сообщений
    768
    Сказал(а) спасибо
    319
    Поблагодарили 339 раз(а) в 268 сообщениях
    Записей в блоге
    6
    Давно хотел написать что-то похожее на Map (словари) как в С++ или других языках.

    Принцип словаря:

    1) Значения заносятся вместе с ключом, который должен быть индивидуальным. Если будет попытка заполнения с повторяющимся ключом, то заполнения этого ключа со значением не произойдет.
    2) Получение значения происходит по ключу
    3) Так же можно получить все значения словаря, при этом они будут возвращены в отсортированном виде.
    4) Если значение в словарь было отправлено с определенным типом, то и получать нужно в такой же тип. Иначе будет возвращен ноль.
    5) Для словаря сделаны 3 типа: Double, Integer , String

    Код :
    ReDim Shared SortMapS() As String
     
    ReDim Shared SortMapI() As Integer
     
    ReDim Shared SortMapD() As Double
     
    Namespace MapOOP
     
    	Type TChildMap
     
    		pNext As TChildMap Ptr
     
    		pPrev As TChildMap Ptr
     
    		szKey As ZString*256
     
    		sValue As ZString*256
     
    		iValue As Integer
     
    		dValue As Double
     
    	End Type
     
    	Type TMap
     
    		iCount As Integer
     
    		iCurrent As Integer
     
    		pFirst As TChildMap Ptr
     
    		pLast As TChildMap Ptr
     
    		Declare Destructor()
     
    		Declare Sub Add(szKey As String , sValue As String)
     
    		Declare Sub Add(szKey As String , sValue As Integer)
     
    		Declare Sub Add(szKey As String , sValue As Double)
     
    		Declare Sub Del (szKey As String)
     
    		Declare Sub Clear()
     
    		Declare Sub Get(szKey As String, ByRef sReturnValue As String)
     
    		Declare Sub Get(szKey As String, ByRef iReturnValue As Integer)
     
    		Declare Sub Get(szKey As String, ByRef dReturnValue As Double)
     
    		Declare Sub GetNext(ByRef sReturnValue As String)
     
    		Declare Sub GetNext(ByRef iReturnValue As Integer)
     
    		Declare Sub GetNext(ByRef dReturnValue As Double)
     
    		Declare Sub Reset()
     
    	End Type
     
    	' ---------------------Добавление в словарь-------------------
    	#Macro MACRO_MAP_ADD( M_TYPE , M_VALUE )
     
    		Sub TMap.Add(szKey As String , Value As M_TYPE)
     
    			Dim pCheck As TChildMap Ptr = pFirst
     
    			Do While pCheck
     
    				If pCheck->szKey = szKey  Then
     
    					Exit Sub
     
    				EndIf
     
    				pCheck = pCheck->pNext
     
    			Loop
     
    			Dim pTemp As TChildMap Ptr = New TChildMap
     
    			M_VALUE = Value
     
    			pTemp->szKey = szKey
     
    			If pFirst = 0 Then
     
    				pFirst = pTemp
     
    			Else
     
    				pLast->pNext = pTemp
     
    				pTemp->pPrev = pLast
     
    			EndIf
     
    			pLast = pTemp
     
    			iCount+=1
     
    		End Sub
     
    	#EndMacro
     
    	MACRO_MAP_ADD(String,pTemp->sValue)
     
    	MACRO_MAP_ADD(Integer,pTemp->iValue)
     
    	MACRO_MAP_ADD(Double,pTemp->dValue)
    	'////////////////////////////////////////////////////////////////
     
     
    	' ---------------------Получение значения по заданному ключу-------------------
    	#Macro MACRO_MAP_GET( M_TYPE , M_VALUE )
     
    		Sub TMap.Get(szKey As String, ByRef ReturnValue As M_TYPE)
     
    			Dim As M_TYPE TempClear
     
    			ReturnValue = TempClear
     
    			Dim pTemp As TChildMap Ptr
     
    			pTemp = pFirst
     
    			Do While pTemp
     
    				If pTemp->szKey = szKey  Then
     
    					ReturnValue = M_VALUE
     
    					Exit Sub
     
    				EndIf
     
    				pTemp = pTemp->pNext
     
    			Loop
     
    		End Sub
     
    	#EndMacro
     
    	MACRO_MAP_GET(String,pTemp->sValue)
     
    	MACRO_MAP_GET(Integer,pTemp->iValue)
     
    	MACRO_MAP_GET(Double,pTemp->dValue)
    	'////////////////////////////////////////////////////////////////
     
     
    	' ---------------------Сброс счетчика массива-------------------
    	Sub TMap.Reset()
     
    		iCurrent = 0
     
    	End Sub
    	'////////////////////////////////////////////////////////////////
     
     
    	#Macro MACRO_MAP_GETNEXT( M_TYPE , M_NAME_ARRAY , M_NAME_PROC, M_VALUE)
     
    		' ---------------------Сортировка-------------------
    		Sub M_NAME_PROC(start As Integer,Finish As Integer)
     
    			Dim As Integer I=start,J=Finish
     
    			Dim As M_TYPE X = M_NAME_ARRAY(Int((I+J)/2)),A
     
    			While  I <= J
     
    				While M_NAME_ARRAY(I) < X
     
    					I+=1
     
    				Wend
     
    				While M_NAME_ARRAY(J) > X
     
    					J-=1
     
    				Wend
     
    				If I<=J Then
     
    					A = M_NAME_ARRAY(I)
     
    					M_NAME_ARRAY(I) = M_NAME_ARRAY(J)
     
    					M_NAME_ARRAY(J) = A
     
    					I+=1
     
    					J-=1
     
    				EndIf
     
    			Wend
     
    			If J > Start Then M_NAME_PROC(start,J)
     
    			If I < Finish Then M_NAME_PROC(I,Finish)
     
    		End Sub
    		'////////////////////////////////////////////////////////////////
     
     
    		' ---------------------Получение отсортированных значений по порядку-------------------
    		Sub TMap.GetNext(ByRef ReturnValue As M_TYPE)
     
    			Dim As M_TYPE TempClear
     
    			ReturnValue = TempClear
     
    			If iCurrent = 0 Then
     
    				ReDim M_NAME_ARRAY(iCount-1) As M_TYPE
     
    				Dim pTemp As TChildMap Ptr
     
    				Dim As Integer i
     
    				pTemp = pFirst
     
    				Do While pTemp
     
    					M_NAME_ARRAY(i) = M_VALUE
     
    					pTemp = pTemp->pNext
     
    					i+=1
     
    				Loop
     
    				M_NAME_PROC(0,iCount-1)
     
    			EndIf
     
    			If iCurrent <= iCount-1 Then
     
    				ReturnValue = M_NAME_ARRAY(iCurrent)
     
    				iCurrent+=1
     
    			EndIf
     
    		End Sub
     
    	#EndMacro
    	'////////////////////////////////////////////////////////////////
     
     
    	MACRO_MAP_GETNEXT(String,SortMapS,QSORTS, pTemp->sValue)
     
    	MACRO_MAP_GETNEXT(Integer,SortMapI,QSORTI, pTemp->iValue)
     
    	MACRO_MAP_GETNEXT(Double,SortMapD,QSORTD, pTemp->dValue)
     
    	' -----------------------Удаление одного ключа из словаря--------------------
    	Sub TMap.Del (szKey As String)
     
    		Dim pTemp As TChildMap Ptr
     
    		pTemp = pFirst
     
    		Do While pTemp
     
    			If pTemp->szKey = szKey  Then
     
    				If pTemp = pFirst Then
     
    					pFirst = pFirst->pNext
     
    				Else
     
    					pTemp->pPrev->pNext = pTemp->pNext
     
    				End If
     
    				If pLast = pTemp Then
     
    					pLast = pLast->pPrev
     
    				Else
     
    					pTemp->pNext->pPrev = pTemp->pPrev
     
    				End If
     
    				Delete pTemp
     
    				iCount-=1
     
    				Exit Sub
     
    			End If
     
     
    			pTemp = pTemp->pNext
     
    		Loop
     
    	End Sub
    	'////////////////////////////////////////////////////////////////
     
     
    	' -----------------------Удаление словаря--------------------
    	Destructor TMap()
     
    		this.Clear()
     
    	End Destructor
    	'////////////////////////////////////////////////////////////////
     
     
    	' -----------------------Очистка словаря--------------------
    	Sub TMap.Clear()
     
    		Dim pTemp As TChildMap Ptr
     
    		Dim pDel As TChildMap Ptr = pFirst
     
    		If pDel Then
     
    			Do
     
    				pTemp = pDel->pNext
     
    				Delete pDel
     
    				pDel = pTemp
     
    			Loop While pTemp<>0
     
    			pFirst = 0
     
    			pLast = 0
     
    			iCount = 0
     
    			ReDim SortMapS(0) As String
     
    			ReDim SortMapI(0) As Integer
     
    			ReDim SortMapD(0) As Double
     
    		EndIf
     
     
    	End Sub
    	'////////////////////////////////////////////////////////////////
     
    End Namespace

    И конечно примеры:

    Код :
    Using MapOOP ' открываем пространство имен
     
    Dim map As TMap Ptr = New TMap ' создаем словарь
     
    ' Заносим три значения в словарь
    map->Add("en","English Language")
     
    map->Add("ru","Russian Language")
     
    map->Add("ge","German Language")
     
    Dim As string sRet ' переменная куда будет возвращаться результат
     
    map->Get("ge",sRet) ' получаем значение с ключом "ge"
     
    ? sRet ' выводим его в консоль
     
    map->Get("en",sRet) ' получаем значение с ключом "en"
     
    ? sRet ' выводим его в консоль
     
    Sleep

    Код :
    Using MapOOP ' открываем пространство имен
     
    Dim map As TMap Ptr = New TMap ' создаем словарь
     
    ' Загоняем 100 случайных значений с ключами от 1 до 100
    For i As Integer  = 1 To 100
     
        map->Add(Str(i),i*rnd)
     
    Next
     
    Dim As double dRet ' переменная куда будет возвращаться результат
     
    map->Reset ' сбрасываем словарь на начало, необходимо перед выводом всех значений
     
    ' проходим по всему словарю , map->iCount - это кол-во записей в словаре
    ' значения будут отсортированы
    For i As Integer = 1 To map->iCount
     
    	map->GetNext(dRet) ' получаем значение
     
    	? dRet ' выводим его в консоль
     
    Next
     
    Sleep
    Ответить с цитированием  
     

  2. 3 пользователя(ей) сказали cпасибо:

    >Quiet Snow< (08.02.2014), Dispetcher14 (08.02.2014), Абадябер (08.02.2014)

  3. #2  
    Гуру Аватар для Абадябер
    Регистрация
    09.12.2010
    Адрес
    Беларусь, Минск
    Сообщений
    1,219
    Сказал(а) спасибо
    302
    Поблагодарили 176 раз(а) в 144 сообщениях
    Записей в блоге
    5
    Спасибо, реализация этой структуры данных может пригодиться, да и сама она
    Дружба-магия-радость!
    Ответить с цитированием  
     

  4. #3  
    Супер модератор Аватар для >Quiet Snow<
    Регистрация
    11.04.2011
    Адрес
    Планета земля
    Сообщений
    3,822
    Сказал(а) спасибо
    1,808
    Поблагодарили 933 раз(а) в 795 сообщениях
    Записей в блоге
    1
    Спасибо Стас, для портажа людям полезно будет. Я то картами никогда не пользовался и скорее всего не буду.
    Обучение прикладному программированию(по skype), качественно, недорого, 18+, вопросы в личку.
    «Если вы ничего не сделаете, я уверяю вас, ничего и не произойдёт» © Жак Фреско
    Ограниченно модерирую.
    Ответить с цитированием  
     

  5. #4  
    Профи Аватар для stabud
    Регистрация
    05.01.2013
    Сообщений
    768
    Сказал(а) спасибо
    319
    Поблагодарили 339 раз(а) в 268 сообщениях
    Записей в блоге
    6
    Да забыл написать, в словаре предусмотрено удаление любой записи по ключу, а так же очистка словаря. Примеры писать для этого не буду, там все просто:

    map->Clear() ' очистка всего словаря

    map->Del (Key) ' удаление любой записи из словаря по ключу

    Вообще хочется , чтобы контейнерные классы (списки, словари, множества, векторы, очереди) внесли сами разработчики на уровне компиля .
    Ответить с цитированием  
     

  6. #5  
    Профи
    Регистрация
    09.11.2013
    Сообщений
    218
    Сказал(а) спасибо
    17
    Поблагодарили 75 раз(а) в 50 сообщениях
    Почему процедуру Get не оформить в виде функции? Это было бы логичнее
    Ответить с цитированием  
     

  7. #6  
    Профи Аватар для stabud
    Регистрация
    05.01.2013
    Сообщений
    768
    Сказал(а) спасибо
    319
    Поблагодарили 339 раз(а) в 268 сообщениях
    Записей в блоге
    6
    Цитата Сообщение от ur_naz Посмотреть сообщение
    Почему процедуру Get не оформить в виде функции? Это было бы логичнее
    То есть имеется ввиду типа value = Get(Key) ?

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

    То есть в лучшем случае это будет так:

    Значение Integer = Get (значение String , значение Integer)
    Значение String = Get (значение String , значение String)
    Значение Double = Get (значение String , значение Double)

    То есть получается, что второй параметр будет равен возвращаемому значению или по крайней мере придется отсылать туда любое значение соответствующего типа. Это как бы вообще через одно место. А без второго параметра перегрузка работать не будет. Так зачем тогда городить огород? Многие WinApi работают таким способом как у меня, например CharToOem , никто не жалуется

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

  8. #7  
    Профи Аватар для rrrFer
    Регистрация
    01.08.2013
    Сообщений
    561
    Сказал(а) спасибо
    34
    Поблагодарили 248 раз(а) в 164 сообщениях
    Я не смотрел внутрь, потому что бэйсик не помню. Но "Принцип словаря:" из первого поста не отражает сути.

    Ты в чем данные то хранишь? - словарь - это дерево (красно-черное или АВЛ), и никак иначе.

    Что такое "5) Для словаря сделаны 3 типа: Double, Integer , String" я тоже не понял. Значит ли это (мне кажется, значит) что каждый узел словаря содержит 3 значения?
    [Ссылки могут видеть только зарегистрированные пользователи. ] // программирование на Prolog, Erlang, C++
    Ответить с цитированием  
     

  9. #8  
    Профи Аватар для stabud
    Регистрация
    05.01.2013
    Сообщений
    768
    Сказал(а) спасибо
    319
    Поблагодарили 339 раз(а) в 268 сообщениях
    Записей в блоге
    6
    Цитата Сообщение от rrrFer Посмотреть сообщение
    Я не смотрел внутрь, потому что бэйсик не помню. Но "Принцип словаря:" из первого поста не отражает сути.

    Ты в чем данные то хранишь? - словарь - это дерево (красно-черное или АВЛ), и никак иначе.

    Что такое "5) Для словаря сделаны 3 типа: Double, Integer , String" я тоже не понял. Значит ли это (мне кажется, значит) что каждый узел словаря содержит 3 значения?
    Я искал информацию по алгоритму создания словаря, но видно она вся прошла мимо меня. За подсказку спасибо, почитаю про эти алгоритмы. И да тебе правильно кажется, каждый узел содержит все три типа. Но что поделаешь, когда я не знаю теории и не могу ее найти , я делаю так , как могу сам придумать.
    Ответить с цитированием  
     

  10. #9  
    Профи Аватар для rrrFer
    Регистрация
    01.08.2013
    Сообщений
    561
    Сказал(а) спасибо
    34
    Поблагодарили 248 раз(а) в 164 сообщениях
    [Ссылки могут видеть только зарегистрированные пользователи. ]
    Там есть книжка Скиены. В ней я вроде бы видел нужную информацию (надеюсь не ошибаюсь).

    Но если коротко, то и у Макконелла есть. Самое главное что должен обеспечить словарь - это логарифмическую сложность поиска нужного элемента (и доступа к нему) и логарифмическое время добавления нового элемента в словарь.

    Чтобы время было логарифмическим надо хранить данные упорядоченными (иначе никак).

    Если данные хранятся в списке (как у тебя) - то время всегда будет линейным (даже если список упорядоченный), а это не годится.

    Если данные лежат в массиве и отсортированы - то логарифмическое время получить можно, но как добавлять новые элементы? - вообще никак - тоже не годится.

    Поэтому данные помещают в дерево. Дерево строится так, что оно упорядочено (обычно так и делают). Если даже помещать данные в обычное дерево -то в среднем случае время будет логарифмическим (и это уже хорошо), НО надо посмотреть на худший случай.

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

    Поэтому дерево надо балансировать, т.е. следить за тем, чтобы количество элементов в левом поддереве не более чем на единицу отличалось от количества элементов в правом поддереве. Это условие должно выполняться рекурсивно для каждого поддерева).

    Но балансировка - это достаточно сложная и долгая и сложная операция. ОДНАКО, есть хитроумные решения (их много разных и еще мильон модификаций), но основные - это красно-черные деревья и АВЛ-деревья. Хотя, вот сейчас посмотрел у Скиены - он пишет что хэштаблицы - тоже вариант (но он отмечает недостатки), про АВЛ и красно-черные - ничего не пишет, но в STL C++ вроде бы они используются.

    И да тебе правильно кажется, каждый узел содержит все три типа.
    Ну это с алгоритмом не связано. Я не знаю бэйсик - не смогу помочь, но неужели в бейсике нет шаблонов как в плюсах? - я погуглил - не нашел. Я нашел тип variant, МБ его использовать можно? - но я слабо представляю как это может быть.
    С другой стороны нагуглил вот это: [Ссылки могут видеть только зарегистрированные пользователи. ]
    это очередь от микрософта в VB. Мне кажется, что в их очередь можно и числа и строки, и еще что-нибудь положить. Надо узнать как они это сделали и сделать также ))
    [Ссылки могут видеть только зарегистрированные пользователи. ] // программирование на Prolog, Erlang, C++
    Ответить с цитированием  
     

  11. Пользователь сказал cпасибо:

    stabud (10.02.2014)

  12. #10  
    Профи Аватар для rrrFer
    Регистрация
    01.08.2013
    Сообщений
    561
    Сказал(а) спасибо
    34
    Поблагодарили 248 раз(а) в 164 сообщениях
    Удивительно что в стандартной поставке бэйсика нет словарей. Я поражен xD.
    Вот тут вроде бы рассказывают как их можно к бэйсику прикрутить: [Ссылки могут видеть только зарегистрированные пользователи. ]

    Я вообще никогда не гуглил ничего про бэйсик, но вот попробовал и гугл меня добил. Почему я гуглю контейнеры basic, а мне предлагают все что угодно, но не то, что нужно. Я получил и какие-то пластикове контейнеры и даже детские горшки. "очередь basic" результатов тоже не дала, как и всякие попытки с "visual basic" и "VB". Мой вывод - в корпорации гугл бэйсик не любят и топят специально ))
    [Ссылки могут видеть только зарегистрированные пользователи. ] // программирование на Prolog, Erlang, C++
    Ответить с цитированием  
     

  13. Пользователь сказал cпасибо:

    stabud (10.02.2014)

Страница 1 из 5 123 ... ПоследняяПоследняя
Информация о теме
Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. Ответов: 4
    Последнее сообщение: 22.02.2012, 21:11
  2. Ответов: 5
    Последнее сообщение: 24.11.2010, 18:30
Ваши права
  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •