Linked List Eintrag schneller suchen

Kaeru Gaman · Beitrag von **Kaeru Gaman** » 17.07.2007 15:31

wenn die liste sortiert ist und ich per indizes zugreifen kann,
brauche ich auch kein zusätzliches array mehr.

ich suche dann ganz einfach index-binär, das ist babarisch schnell.

bei einer tabelle mit bis zu 2^n elementen brauche ich maximal n+1 zugriffe, um das element zu finden.

sowas geht dann aber nicht mit einer LL unter PB sondern dafür brauche ich ein Array (zugriff über Indizes)

noch ne andere methode wären Hashtables.
sucht mal im forum, NTQ hat dazu mal einiges gepostet...

edel · Beitrag von **edel** » 17.07.2007 15:50

Schaut euch mal das hier an : http://home.gna.org/gdsl/ bzw http://home.gna.org/gdsl/1.4/html/modules.html .

Damit laesst es sich sehr gut arbeiten. Falls Interesse besteht
kann ich auch die fertige Lib und nen PB Beispiel posten.

dysti · Beitrag von **dysti** » 17.07.2007 16:39

@edel, also ich hätte Interesse. Wichtig das PB-Beispiel.

edel · Beitrag von **edel** » 17.07.2007 22:39

www.edel.basicguru.net/bin/gdsl/gdsl.lib

Code: Alles auswählen


Enumeration-1
  #GDSL_ERR_MEM_ALLOC
  #GDSL_MAP_STOP
  #GDSL_MAP_CONT
  #GDSL_INSERTED
  #GDSL_FOUND
EndEnumeration

;- Hashtable manipulation module
ImportC "gdsl.lib"
  gdsl_hash(key.s)
  gdsl_hash_alloc(name.s,ALLOC_F,FREE_F,KEY_F,HASH_F,INITIAL_ENTRIES_NB)
  gdsl_hash_free(H)
  gdsl_hash_flush(H)
  gdsl_hash_get_name(H)
  gdsl_hash_get_entries_number(H)
  gdsl_hash_get_lists_max_size(H)
  gdsl_hash_get_longest_list_size(H)
  gdsl_hash_get_size(H)
  gdsl_hash_get_fill_factor.d(H)
  gdsl_hash_set_name(H,HASHNAME.s)
  gdsl_hash_insert(H,key.l)
  gdsl_hash_remove(H,key.l)
  gdsl_hash_delete(H,key.l)
  gdsl_hash_modify(H,NEW_ENTRIES_NB.w,NEW_LISTS_MAX_SIZE.w)
  gdsl_hash_search(H,key.l)
  gdsl_hash_map(H,MAP_F,*USER_DATA)
  gdsl_hash_write(H,WRITE_F,OUTPUT_FILE,*USER_DATA)
  gdsl_hash_write_xml(H,WRITE_F,OUTPUT_FILE,*USER_DATA)
  gdsl_hash_dump(H,WRITE_F,OUTPUT_FILE,*USER_DATA)
EndImport

;- Stack manipulation module
ImportC "gdsl.lib"
  gdsl_stack_alloc(name.s,ALLOC_F,FREE_F)
  gdsl_stack_free(s)
  gdsl_stack_get_name(s)
  gdsl_stack_get_size(s)
  gdsl_stack_get_growing_factor(s)
  gdsl_stack_get_top(s)
  gdsl_stack_get_bottom(s)
  gdsl_stack_set_growing_factor(s)
  gdsl_stack_insert(s,*VALUE)
  gdsl_stack_remove(s)
  gdsl_stack_search(s,COMP_F,*VALUE)
  gdsl_stack_search_by_position(s,POS)
  gdsl_stack_map_forward(s,MAP_F,*USER_DATA)
  gdsl_stack_map_backward(s,MAP_F,*USER_DATA)
  gdsl_stack_write(s,WRITE_F,OUTPUT_FILE,*USER_DATA)
  gdsl_stack_write_xml(s,WRITE_F,OUTPUT_FILE,*USER_DATA)
  gdsl_stack_dump(s,WRITE_F,OUTPUT_FILE,*USER_DATA)
  gdsl_stack_flush(s)
  gdsl_stack_is_empty(s)
  gdsl_stack_set_name(s,NEWNAME.s)
EndImport

;- 2D-Arrays manipulation module
ImportC "gdsl.lib"
  gdsl_2darray_alloc(name.s,ROW,COL,ALLOC_F,FREE_F)
  gdsl_2darray_free(A)
  gdsl_2darray_get_name(A)
  gdsl_2darray_get_rows_number(A)
  gdsl_2darray_get_columns_number(A)
  gdsl_2darray_get_size(A)
  gdsl_2darray_get_content(A,ROW,COL)
  gdsl_2darray_set_content(A,ROW,COL)
  gdsl_2darray_set_name(A,NEW_NAME.s)
  gdsl_2darray_write(A,WRITE_F,OUTPUT_FILE,USER_DATA)
  gdsl_2darray_write_xml(A,WRITE_F,OUTPUT_FILE,USER_DATA)
  gdsl_2darray_dump(A,WRITE_F,OUTPUT_FILE,USER_DATA)
EndImport

;- Red-blacktree manipulation module
ImportC "gdsl.lib"
  gdsl_rbtree_alloc(name.s,ALLOC_F,FREE_F,COMP_F)
  gdsl_rbtree_free(T)
  gdsl_rbtree_flush(T)
  gdsl_rbtree_get_name(T)
  gdsl_rbtree_is_empty(T)
  gdsl_rbtree_get_root(T)
  gdsl_rbtree_get_size(T)
  gdsl_rbtree_height(T)
  gdsl_rbtree_set_name(T,NEWNAME.s)
  gdsl_rbtree_insert(T,*VALUE,*RESULT)
  gdsl_rbtree_remove(T,*VALUE)
  gdsl_rbtree_delete(T,*VALUE)
  gdsl_rbtree_search(T,COMP_F,*VALUE)
  gdsl_rbtree_map_prefix(T,MAP_F,*USER_DATA)
  gdsl_rbtree_map_infix(T,MAP_F,*USER_DATA)
  gdsl_rbtree_map_postfix(T,MAP_F,*USER_DATA)
  gdsl_rbtree_write(T,WRITE_F,OUTPUT_FILE,*USER_DATA)
  gdsl_rbtree_write_xml(T,WRITE_F,OUTPUT_FILE,*USER_DATA)
  gdsl_rbtree_dump(T,WRITE_F,OUTPUT_FILE,*USER_DATA)
EndImport

;- Queue manipulation module
ImportC "gdsl.lib"
  gdsl_queue_alloc(name.s,ALLOC_F,FREE_F)
  gdsl_queue_free(Q)
  gdsl_queue_get_name(Q)
  gdsl_queue_get_size(Q)
  gdsl_queue_get_head(Q)
  gdsl_queue_get_tail(Q)
  gdsl_queue_set_name(Q,NEWNAME.s)
  gdsl_queue_insert(Q,*VALUE)
  gdsl_queue_remove(Q)
  gdsl_queue_search(Q,COMP_F,*VALUE)
  gdsl_queue_search_by_position(Q,POS)
  gdsl_queue_map_forward(Q,MAP_F,*USER_DATA)
  gdsl_queue_map_backward(Q,MAP_F,*USER_DATA)
  gdsl_queue_write(Q,WRITE_F,OUTPUT_FILE,*USER_DATA)
  gdsl_queue_write_xml(Q,WRITE_F,OUTPUT_FILE,*USER_DATA)
  gdsl_queue_dump(Q,WRITE_F,OUTPUT_FILE,*USER_DATA)
  gdsl_queue_flush(Q)
  gdsl_queue_is_empty(Q)
EndImport

;- Binary search tree manipulation module
ImportC "gdsl.lib"
  gdsl_bstree_alloc(name.s,ALLOC_F,FREE_F,COMP_F)
  gdsl_bstree_free(T)
  gdsl_bstree_flush(T)
  gdsl_bstree_get_name(T)
  gdsl_bstree_is_empty(T)
  gdsl_bstree_get_root(T)
  gdsl_bstree_get_size(T)
  gdsl_bstree_get_height(T)
  gdsl_bstree_set_name(T,name.s)
  gdsl_bstree_insert(T,*VALUE,*RESULT)
  gdsl_bstree_remove(T,*VALUE)
  gdsl_bstree_delete(T,*VALUE)
  gdsl_bstree_search(T,COMP_F,*VALUE)
  gdsl_bstree_map_prefix(T,MAP_F,*USER_DATA)
  gdsl_bstree_map_infix(T,MAP_F,*USER_DATA)
  gdsl_bstree_map_postfix(T,MAP_F,*USER_DATA)
  gdsl_bstree_write(T,WRITE_F,OUTPUT_FILE,USER_DATA)
  gdsl_bstree_write_xml(T,WRITE_F,OUTPUT_FILE,USER_DATA)
  gdsl_bstree_dump(T,WRITE_F,OUTPUT_FILE,USER_DATA)
EndImport

;- Low-level doubly-linkednode manipulation module
ImportC "gdsl.lib"
  _gdsl_node_alloc()
  _gdsl_node_free(node)
  _gdsl_node_get_succ(node)
  _gdsl_node_get_pred(node)
  _gdsl_node_get_content(node)
  _gdsl_node_set_content(node,content)
  _gdsl_node_set_succ(node,SUCC)
  _gdsl_node_set_pred(node,PRED) 
  _gdsl_node_link(NODE1,NODE2)
  _gdsl_node_unlink(NODE1,NODE2)
  _gdsl_node_write(node,WRITE_F,OUTPUT_FILE,*USER_DATA)
  _gdsl_node_write_xml(node,WRITE_F,OUTPUT_FILE,*USER_DATA)
  _gdsl_node_dump(node,WRITE_F,OUTPUT_FILE,*USER_DATA)
EndImport


;- Low-level doubly-linkedlist manipulation module
ImportC "gdsl.lib"
  _gdsl_list_alloc(name.s)
  _gdsl_list_free(L,FREE_F)
  _gdsl_list_is_empty(L)
  _gdsl_list_get_size(L)
  _gdsl_list_link(L1,L2)
  _gdsl_list_insert_after(L,PREV)
  _gdsl_list_insert_before(L,SUCC)
  _gdsl_list_remove(node)
  _gdsl_list_search(L,COMP_F,*VALUE)
  _gdsl_list_map_forward(L,MAP_F,*USER_DATA)
  _gdsl_list_map_backward(L,MAP_F,*USER_DATA)
  _gdsl_list_write(L,WRITE_F,OUTPUT_FILE,*USER_DATA)
  _gdsl_list_write_xml(L,WRITE_F,OUTPUT_FILE,*USER_DATA)
  _gdsl_list_dump(L,WRITE_F,OUTPUT_FILE,*USER_DATA)
EndImport


;- Doubly-linkedlist manipulation module
ImportC "gdsl.lib"
  gdsl_list_alloc(name.s,ALLOC_F,FREE_F)
  gdsl_list_free(L)
  gdsl_list_get_name(L)
  gdsl_list_get_size(L)
  gdsl_list_get_head(L)
  gdsl_list_get_tail(L)
  gdsl_list_insert_head(L,*VALUE)
  gdsl_list_insert_tail(L,*VALUE)
  gdsl_list_remove_head(L)
  gdsl_list_remove_tail(L)
  gdsl_list_delete_head(L)
  gdsl_list_delete_tail(L)
  gdsl_list_remove(L,COMP_F,*VALUE)
  gdsl_list_delete(L)
  gdsl_list_search(L,COMP_F,*VALUE)
  gdsl_list_search_by_position(L,POS)
  gdsl_list_search_max(L,COMP_F)
  gdsl_list_search_min(L,COMP_F)
  gdsl_list_sort(L,COMP_F)
  gdsl_list_map_forward(L,MAP_F,*USER_DATA)
  gdsl_list_map_backward(L,MAP_F,*USER_DATA)
  gdsl_list_write(L,WRITE_F,OUTPUT_FILE,*USER_DATA)
  gdsl_list_write_xml(L,WRITE_F,OUTPUT_FILE,*USER_DATA)
  gdsl_list_dump(L,WRITE_F,OUTPUT_FILE,*USER_DATA)
  gdsl_list_cursor_alloc(L)
  gdsl_list_cursor_free(C)
  gdsl_list_cursor_move_to_head(C)
  gdsl_list_cursor_move_to_tail(C)
  gdsl_list_cursor_move_to_value(C,COMP_F,*VALUE)
  gdsl_list_cursor_move_to_position(C,POS)
  gdsl_list_cursor_step_forward(C)
  gdsl_list_cursor_step_backward(C)
  gdsl_list_cursor_is_on_head(C)
  gdsl_list_cursor_is_on_tail(C)
  gdsl_list_cursor_has_succ(C)
  gdsl_list_cursor_has_pred(C)
  gdsl_list_cursor_set_content(C,E)
  gdsl_list_cursor_get_content(C)
  gdsl_list_cursor_insert_after(C,*VALUE)
  gdsl_list_cursor_insert_before(C,*VALUE)
  gdsl_list_cursor_remove(C)
  gdsl_list_cursor_remove_after(C)
  gdsl_list_cursor_remove_before(C)
  gdsl_list_cursor_delete(C)
  gdsl_list_cursor_delete_after(C)
  gdsl_list_cursor_delete_before(C)
  gdsl_list_flush(L)
  gdsl_list_is_empty(L)
  gdsl_list_set_name(L,name.s)
EndImport

;- Permutation manipulation module
ImportC "gdsl.lib"
  gdsl_perm_alloc(name.s,ALLOC_F,FREE_F,COMP_F)
  gdsl_perm_free(p)
  gdsl_perm_copy(p)
  gdsl_perm_get_name(p)
  gdsl_perm_get_size(p)
  gdsl_perm_get_element(p,index)
  gdsl_perm_get_elements_array(p)
  gdsl_perm_linear_inversions_count(p)
  gdsl_perm_linear_cycles_count(p)
  gdsl_perm_canonical_cycles_count(p)
  gdsl_perm_linear_next(p)
  gdsl_perm_linear_prev(p)
  gdsl_perm_set_elements_array(p,*ARRAY)
  gdsl_perm_multiply(RESULT,ALPHA,BETA)
  gdsl_perm_linear_to_canonical(Q,p)
  gdsl_perm_canonical_to_linear(Q,p)
  gdsl_perm_inverse(p)
  gdsl_perm_reverse(p)
  gdsl_perm_randomize(p)
  gdsl_perm_apply_on_array(*V,p)
  gdsl_perm_write(p,WRITE_F,OUTPUT_FILE,*USER_DATA)
  gdsl_perm_write_xml(p,WRITE_F,OUTPUT_FILE,*USER_DATA)
  gdsl_perm_dump(p,WRITE_F,OUTPUT_FILE,*USER_DATA)
  gdsl_perm_set_name(p,name.s)
EndImport

;- Sort module
ImportC "gdsl.lib"
  gdsl_sort(T,N,COMP_F)
EndImport

;- Main module
ImportC "gdsl.lib"
  gdsl_get_version()
EndImport

Beipdings :

Code: Alles auswählen

Structure HTElement
  key.l
  uData.l
EndStructure

Structure HTInfo
  cb.l
  HT.l
  uData.l
EndStructure

ImportC ""
  free(mem)
EndImport

;- 
ProcedureC ht_alloc(key.l)
  Protected *obj.HTElement  = LocalAlloc_(#LMEM_ZEROINIT,SizeOf(HTElement));AllocateMemory(SizeOf(HTElement))
  *obj\key = key
  ProcedureReturn *obj
EndProcedure
;- 
ProcedureC ht_key(*obj.HTElement)
  ProcedureReturn *obj\key	
EndProcedure
;- 
ProcedureC ht_free(*obj.HTElement)
  free(*obj\key)
  LocalFree_(*obj)
EndProcedure
;- 
ProcedureC NewHashTable(name.s="null")
  HT = gdsl_hash_alloc(name,@ht_alloc(),@ht_free(),@ht_key(),0,11)
  gdsl_hash_modify(HT,1,1)
  ProcedureReturn HT
EndProcedure
;- 
ProcedureC HTGet(HT,key.s)
  Protected *obj.HTElement
  
  If key
    
    *obj = gdsl_hash_search(HT,@key)
    
    If *obj 
      ProcedureReturn *obj\uData
    EndIf
    
  EndIf
  
EndProcedure
;- 
ProcedureC HTSet(HT,key.s,value)
  Protected *obj.HTElement
  Protected dupKey
  
  If key
    
    *obj = gdsl_hash_search(HT,@key)
    
    If Not *obj
      dupKey = strdup_(@key)
      *obj = gdsl_hash_insert(HT,dupKey)  
    EndIf
    
    If *obj And value
      *obj\uData = value
    EndIf 
    
  EndIf
  
EndProcedure
;- 
ProcedureC HTSize(HT) 
  ProcedureReturn gdsl_hash_get_size(HT)
EndProcedure
;- 
ProcedureC HTFlush(HT)
  ProcedureReturn gdsl_hash_flush(HT)
EndProcedure
;- 
ProcedureC HTDelete(HT,key.l)
  ProcedureReturn gdsl_hash_delete(HT,key)
EndProcedure
;-
ProcedureC _ht_callback(*obj.HTElement,loc,*uData.HTInfo) 
  ProcedureReturn CallCFunctionFast(*uData\cb,*uData\HT,*obj\key,*obj\uData,*uData\uData)
EndProcedure
;- 
ProcedureC HT_Map(HT,Callback,uData=0)
  Protected info.HTInfo
  info\cb    = Callback
  info\uData = uData
  info\HT    = HT
  ProcedureReturn gdsl_hash_map(HT,@_ht_callback(),@info) 
EndProcedure
;- 
Procedure HTFree(HT)
  ProcedureReturn gdsl_hash_free(HT)
EndProcedure
;-

Code: Alles auswählen


ProcedureC HashCB(HT,key.s,value,uData)
  Debug key
  Debug value
  Debug "--"
  ProcedureReturn #GDSL_MAP_CONT
EndProcedure

HT = NewHashTable()

HTSet(HT,"Herbert",123456)
HTSet(HT,"Susi",987654)
HTSet(HT,"Bernd",2345)
HTSet(HT,"Olli",35433)

HT_Map(HT,@HashCB())

Debug HTGet(HT,"Herbert")
Debug HTGet(HT,"Susi")
Debug HTGet(HT,"Bernd")
Debug HTGet(HT,"Olli")

HTFlush(HT)
HTFree(HT)

Das ist nur ein bleistift, natuerlich nicht optimal umgestzetzr , es fehlt die unioce hash funktion , aber als beispiel alle mal ausreuchend.

sen-me · Beitrag von **sen-me** » 21.07.2007 22:26

Aaaalso

Maln Beispiel:

Code: Alles auswählen

Structure u
 name.s
 other.s
EndStructure

Global NewList example.u()

Procedure Search(string.s)
 ;...
EndProcedure

AddElement(example())
example()\name = "Test"
example()\other = "Hello World"
AddElement(example())
example()\name = "Other"
example()\other = "I am a program"

Search("Test")
Debug example()\other
End

Also in der Search-Funktion soll er schnell nach dem Begriff suchen (immer im example()\name) und dieses Element auswählen.
Damit kann ich dann was ausgeben oder verwalten.

Kaeru Gaman · Beitrag von **Kaeru Gaman** » 22.07.2007 01:28

Aaaalso

nimm ein array und such index-binär,
oder benutz edels lib.

sen-me · Beitrag von **sen-me** » 27.07.2007 11:46

Wie funktioniert sowas?
Im Array ne Nummer speichern?
Aber im Array muss ich doch auch nach dem begriff suchen, also jedes einzelne durchgehen, oder?

Kaeru Gaman · Beitrag von **Kaeru Gaman** » 27.07.2007 12:15

nein, im Array speicherst du nur deine datensätze, und zwar alphabetisch nach suchbegriff sortiert.

beim suchen springst du jetzt immer in die mitte einem blocks, und zwar folgender maßen:

angenommen, du hast 4000 datensätze, dann springst du zuerst zu
datensatz 2000 (mitte des blockes), und vergleichst den suchbegriff mit "<", ">", "="

wenn er kleiner ist, muss sich der gesuchte in den ersten 2000 befinden,
wenn größer in den letzten 2000.

angenommen er ist kleiner, dann springst du zu datensatz 1000 (mitte des blockes),
dort vergleichst du wieder.

wenn er jetzt größer ist, kann er sich also nur noch zwischen 1000 und 2000 befinden.

wo springst du also hin?

richtig, in die mitte des blockes, und das ist diesmal 1500.

so verfährst du immer weiter, bis du den datensatz schließlich hast.

damit brauchst du wesentlich weniger zugriffe, als wenn du von vorne an durchsuchst.

ich rechne das mal aus für 4000:
2000 > 1000 > 500 > 250 > 125 > 63 > 32 > 16 > 8 > 4 > 2 > 1 > +1
= 13 zugriffe
für jeden datensatz maximal.

wenn du von vorne suchst, brauchst du für die hälfte über tausend zugriffe.