implementation of a tries?

I have to code a TriesConstruct and also a TriesDestruct, how do I do this using that implementation?

Is tries a good data structure to store sorted or unsorted dictionaries

Ok, what's this about ... Are you sure you want a trie ? Do you need to develop this yourself ?

I am reading a sorted list of words and I wan't to take words by words from that line and put it into a tries data structure. Right now I am using a bst to store it, but it's kind of slow.. I was hoping that I can get improvements by changing the data structure into a tries.. any opinions?

>> but it's kind of slow

What is slow ? And how did you measure/compare it ?


>> I have to code a TriesConstruct and also a TriesDestruct, how do I do this using that implementation?

The implementation of the trie I posted looks pretty complete, including the functions you mentioned. Did you look at the source code ?

oh yes it has the tries construct and tries destruct that I need.. however how do I traverse this tries in order??

slow here I compare it using the time feature in unix.. I am supposed to reach a particular time but my current implementation is far beyond.. say it's supposed to be 6 sec to store a words but my implementation takes 1 minute

>> but my implementation takes 1 minute

??? 1 minute to store a word in a data structure ? You've got a serious problem lol.


>> however how do I traverse this tries in order??

A trie is not made to traverse it - it's made for performing lookups (reTRIEvals). That said, you can always traverse it by going over every level of the trie in order.

I see.. so it's kind of hard to traverse a trie..lol.. Is a trie better than a hash table?


>>??? 1 minute to store a word in a data structure ? You've got a serious problem lol.
that's why I am asking here.. I must store the data in somekind of a data structure and then be able to have an iterator that will go rhrough all the data in a sorted order.. right now I am using a threaded BST which is easy to traverse using an iterator and it doesn't have to be recursive

I was thinking of just storing all the data in an array and then do a quick sort on that array then do an iterator on that array that is sorted.. but I am just wondering if this is faster than my current threaded BST

or can you suggest me an idea how to improve this?

>> so it's kind of hard to traverse a trie

It's not hard (just traverse every level of the trie in order) ... It's just not something that is generally done with a trie.


>> I must store the data in somekind of a data structure and then be able to have an iterator that will go rhrough all the data in a sorted order..

You already have it sorted, so why not just store it in an array ?


>> a threaded BST

A threaded BST ? What do you mean ?

no not really actually.. what I am saying is that I have a data and I need to store it in order

>> no not really actually..

What was that a response to ?


>> what I am saying is that I have a data and I need to store it in order

If that's all you want to do, then a simple array is more than sufficient.

yes.. so I am guessing an array would do the work.. to make it more clear.. I am given a list of words and it can be sorted or not.. then I have to iterate over that file in a sorted fashion way.. so you think using an array and do a quicksort on it is good?

>> so you think using an array and do a quicksort on it is good?

If the whole array is not too large (will fit nicely in memory), then an array is a good solution.

I am storing like 5000 words into an array.. is that too big?

Nope. That sounds reasonable.

okay then.. I am going to build an ArrayList to do this.. it's supposed to be very easy just use a dynamic memory allocation whenever I want to insert right?

>> an ArrayList

an ArrayList ?

>> a dynamic memory allocation whenever I want to insert right?

Why ?


Why not use a simple array ?

okay then just use an simple array I guess..

but I don't know the size of the array as I don't know how big the size of the list is

>> as I don't know how big the size of the list is

Then find out the size first :)

then that doesn't make sense as I have to traverse the list of files first and then I know the size and then traverse it back again to get the words.. can I grow the array size dynamically?

>> the list of files

That's the first thing I hear of multiple files ;)


>> can I grow the array size dynamically?

Sure. But I wouldn't do that 1 by one ... Choose an intial size that is "a good guess", and if needed, increase the size by "a fair amount".

okay then.. how do I specify an array of words with a specific size?

>> how do I specify an array of words with a specific size?

Just :

char **words = new char*[size];

                                              

1:

could you please correct my code below, I know there's something wrong.

struct list_el {
  char** head;
  int index;
};
 
typedef struct list_el ArrayList;
 
 
ArrayList* ArrayListConstruct()
{
  ArrayList* this = (ArrayList*)malloc(sizeof(ArrayList));
  this->head = new char*[500];
  this->index = 0;
  return this;
}
 
void ArrayListDestruct(ArrayList* list)
{
  int ii;
  for (ii =0; ii<list->index; ii++){
    StringDestruct(list->head[ii]);
  }
 
  free(list);
}
 
boolean ArrayListInsert(ArrayList* this, char* data)
{
  if (this->index == 500){
    this->head  = realloc(this->head, sizeof(char *) * (this->index + 1));
    bld[bldIndex] = malloc(strlen(pc) + 1);
  }else if{
   this->head[(this->index) + 1] = data;
   this->index = this->index++;
  }
}
                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:

define "something wrong"

I am not sure on the insertion if that's how I do it using dynamic memory allocation

and can you actually do

char **words = new char*[size];

this in C?

>> I am not sure on the insertion if that's how I do it using dynamic memory allocation

Just add it to the end of the array ... Your data is either already sorted or will be sorted after filling the array.


>> and can you actually do

No ;) Sorry :

char **words = (char**) calloc(size, sizeof(char*));

                                              

1:

and here's my last version of my code which still doesn't work when I try to traverse it

can you help me here

#include "list.h"
 
 
int main(){
 
  ArrayList* ar = ArrayListConstruct();
  ArrayListInsert(ar, StringConstruct("haha"));
  ArrayListInsert(ar, StringConstruct("my"));
  ArrayListInsert(ar, StringConstruct("name"));
  ArrayListInsert(ar, StringConstruct("is"));
  ArrayListInsert(ar, StringConstruct("aditya"));
  ArrayListTraverse(ar);
 
 
  return 0;
 
}
 
 
 
 
 
 
 
 
#include "cstr.h"
#include <stdlib.h>
#include <string.h>
 
int_u4 StringHash (const char* key)
{
  int_u4 h = 0;
  if (key!=NULL) {
    for (; *key; key++) {
      h = (h<<3) + ((*key)*(9781623));
    }
  }
  return h;
}
 
char* StringConstruct (const char* s)
{
  char* copy = (char*)malloc(strlen(s)+1);
  strcpy(copy, s);
  return copy;
}
 
void StringDestruct (char* s)
{
  if (s!=0) 
    free(s);
}
 
 
ArrayList* ArrayListConstruct()
{
  ArrayList* this = (ArrayList*)malloc(sizeof(ArrayList));
  this->head = (char**) calloc(500, sizeof(char*));
  this->size = 500;
  this->index = 0;
  return this;
}
 
void ArrayListDestruct(ArrayList* list)
{
  int ii;
  for (ii =0; ii<list->index; ii++){
    StringDestruct(list->head[ii]);
  }
 
  free(list);
}
 
boolean ArrayListInsert(ArrayList* this, char* data)
{
  if (this->index == this->size){
    this->head  = realloc(this->head, sizeof(char *) * (this->index + 1));
    this->index = (this->index)+1;
    this->head[this->index] = data;
    this->size = (this->size)+1;
    return true;
  }else {
   this->head[(this->index) + 1] = data;
   this->index = this->index++;
   return true;
  }
  return false;
}
 
int ArrayListLookup(ArrayList* this, char* data)
{
  return 1;
}
 
void ArrayListTraverse(ArrayList* list)
{
 int ii;
 for (ii = 0; ii<list->index; ii++){
   printf("%s\n", list->head[ii]);
 }
}
 
int compareStrings(const void* p1, const void* p2)
{
  char** s1 = (char**)p1;
  char** s2 = (char**)p2;
  if (strcmp(*s1, *s2)>0){
    return true;
  } else
    return false;
}
                                              

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:

What's ArrayList ?


You forgot to free(this->head); in ArrayListDestruct.


In your ArrayListInsert, you have to be aware that indexing starts at 0, so (this->index == this->size) is not necessarily what you think it is.

>>You forgot to free(this->head); in ArrayListDestruct.


>>In your ArrayListInsert, you have to be aware that indexing starts at 0, so (this->index == this->size) is >>not necessarily what you think it is.

   I just fixed those two problems...

ArrayList is this:


So besides all that it should work right?

struct list_el {
  char** head;
  int index;
  int size;
};
 
typedef struct list_el ArrayList;

                                              

1:
2:
3:
4:
5:
6:
7:

>> So besides all that it should work right?

Test it ;) I just pointed out a few problems I immediately noticed. I might have missed something ... that's what testing is for :)

okay..I'll do some test now

I've got a problem.. why doesn't this work??

it always generates a seg fault

void ArrayListTraverse(ArrayList* list)
{
 qsort(list, list->index, sizeof(char*), compareStrings);
 int ii;
 for (ii = 0; ii<list->index; ii++){
   printf("%s\n", temp->head[ii]);
 }
}
                                              

1:
2:
3:
4:
5:
6:
7:
8:

I fixed the problem above, now I have this problem:

that's a code fragment for the insert part... I think just doesn't do it right

 if (this->index == this->size){
    this->head  = realloc(this->head, sizeof(char *) * (this->index + 1));
    this->index = (this->index)+1;
    this->head[this->index] = data;
    this->size = (this->size)+1;
    return true;
  }

                                              

1:
2:
3:
4:
5:
6:
7:

Did you fix this remark I made earlier ?

>> In your ArrayListInsert, you have to be aware that indexing starts at 0, so (this->index == this->size) is not necessarily what you think it is.

I08,

http://www.experts-exchange.com/Programming/Languages/C/Q_23370460.html#a21496888

Paul

Thanks for that link, Paul. That clarifies quite a lot, and contains important information that kinghalls failed to mention in this post :)

If the problem is to combine two files (one big sorted file, and a smaller unsorted file) into one sorted file, then I would simply sort the unsorted file, and then merge both files into the output file (which will also be sorted as a consequence).


Anyway, I think your original question about trie implementations was answered, correct ? So, all questions regarding what is the most optimal approach for this should go in your other thread (the one Paul posted a link for), because that's the subject of that other question.

I agree I08 but this question is valid and valuable. Use of a trie in this case may produce a near-optimal solution. Many programmers seem to think that there are only three main storage data structures; lists, trees and hashmaps. :(

kinghalls, please try to give as much information as possible about your question, especially with links to related threads. You also need to do some coding. We can fix your problems and guide you in what you want to do but sadly we cannot do it for you.

Paul

I'd like to know if my understanding of the problem is correct : "If the problem is to combine two files (one big sorted file, and a smaller unsorted file) into one sorted file".

Hi I08,

My reading of the question I linked to suggests that this is an assignment to demonstrate the benefits of optimal algorithms and data structures.

They are given one sorted dictionary (potentially large) and one unsorted list of words. They are asked to generate a sorted list of those words that appear in both files.

They must adhere to an interface that looks workable.

Paul

>> that appear in both files

That's the part I missed :) Ignore my suggestions for an array then :)

>>They are given one sorted dictionary (potentially large) and one unsorted list of words. They are asked to >>generate a sorted list of those words that appear in both files.

this is true, however it is not always the case that one is larger and one is smaller.. in one of the test cases.. it takes two similar files which is the same (same words, and of course same size). the first file I read into a hash table (I don't care of the ordering because the purpose of storing this into a hash table is for better lookup). As for the second time, when I read the same file.. I do a hash table lookup to see if that elements exists in the hash table AND I also have to do a lookup in my array to see if it already exists there.. if it exists in the hash table but does not exist in the array then I do an insertion.


After I insert all the words into an array. I will have to be able to traverse them in sorted order (if not it wouldn't be a dictionary). So for the second file, I will need a data structure that needs to be traversed.. As Infinity said a trie is not usual to be traversed. So what would a great data structure here? I am sure for reading the first file choosing a hash table is a correct choice as it only server the purpose for a lookup, which can be done in O(1)...

Just another idea maybe is to sort the second file, and then iterate over both files just once, retaining only the duplicates. No data structure overhead (except for the sorting phase). Might be worth testing for speed.

Infinity08

yes that would be a great idea, but I can't do this as there are some parts of the code that I can't change and it is the steps doing this. The steps MUST be:

1. for each word in the first file, put word into a structure until all the words have been traversed i
2. for each word in the second file, check if it exists in the first file, if not then check if it exists in the
   current data structure.. if both satisfies then put it into the structure.
3. traverse the second structure and then write the words into a new file in sorted order.


those three steps COULD NOT be change whatever happens..

so what now?

>> so what now?

Follow the advice given in your other question ;) That's what that question was about :) This question is about tries.

>>Follow the advice given in your other question ;) That's what that question was about :) This question is >>about tries.

Just one more thing, so do you think using a tries will be a good idea?

>> so do you think using a tries will be a good idea?

Ye, why not ? It's perfectly fine for performing fast lookups. Don't doubt Paul ;)

but a hash table does a similar thing.. right? O(1) lookups?

Big O notation doesn't tell you everything :

1) a hash table has quite a bit of overhead calculating the hashes
2) a hash table can have collisions
3) the data in a hash table is not ordered
4) the operations on a trie are very fast on pretty much all platforms (simple array indexing)

You'll have to test and see which of the two is faster :)

But I'm sure this has already been covered in your other question.

yes.. I understand all that, but we don't need ordered elements in the first structure, we only need to do a simple lookup

So, what's your point ?

so I am confident that hash table is enough

It's nice to be confident. But did you read all 4 points in my previous code ? I wouldn't be so confident, and I'd at least test out both approaches to see which one is faster.

yes.. I just tweak my code so that my hash table size would be larger and now it's got the speed I have