What is the best way to imlement link list of numbers?
What is the best way to imlement link list of numbers?
I am new to C++ so please go easy on the technical jargon. Have a question about linked list - or may be there is a better way to do this.
Here is the idea and I have no idea on how to implement it. Suppose we have a large file with numbers that are entered by users which are mostly repetitive (the numbers, not the users!) Something like this:
12345612345612345678
12345612345612345679
12345612345612345680
12345612345612345681
etc.
Suppose this file is in gigabytes. What I want to do is to take each entered number, decompose it to individual digits, link them somehow, create pointers in memory to their position within the line and then write only the different (new) combination of numbers and their positions.
I realize it would be easier to write the numbers as they are if this was a small amount of data. But what I am trying to do is to speed up writing and reading speed and decrease the space usage.
Questions:
1) What is the best way to do this? Linked lists and memory pointers? Examples?
2) Will space and storage difference be positive?
Thanks a lot!
I am new to C++ so please go easy on the technical jargon. Have a question about linked list - or may be there is a better way to do this.
Here is the idea and I have no idea on how to implement it. Suppose we have a large file with numbers that are entered by users which are mostly repetitive (the numbers, not the users!) Something like this:
12345612345612345678
12345612345612345679
12345612345612345680
12345612345612345681
etc.
Suppose this file is in gigabytes. What I want to do is to take each entered number, decompose it to individual digits, link them somehow, create pointers in memory to their position within the line and then write only the different (new) combination of numbers and their positions.
I realize it would be easier to write the numbers as they are if this was a small amount of data. But what I am trying to do is to speed up writing and reading speed and decrease the space usage.
Questions:
1) What is the best way to do this? Linked lists and memory pointers? Examples?
2) Will space and storage difference be positive?
Thanks a lot!
| write only the different (new) combination of numbers and their positions. |
Maybe I misunderstood you, but you could try a trie.
http://en.wikipedia.org/wiki/Trie
closed account (Lv0f92yv)
Why do you need to decompose them into digits and reference them relative to each digits position in the line?
If you want to only add unique numbers to the list, then for each insertion into the list you can traverse the list to see if the number (line) already exists. This might be slow for really long lists, so alternatively:
Use an array of integers and use a simple binary search for each number/line. Binary search overview:
Consider using a different, more efficient data structure, such as a Binary Search Tree. These are more efficient and pretty easy to implement once you learn the concepts behind them. They give O(logN) search times where N = number of entries in the tree.
If you want to only add unique numbers to the list, then for each insertion into the list you can traverse the list to see if the number (line) already exists. This might be slow for really long lists, so alternatively:
Use an array of integers and use a simple binary search for each number/line. Binary search overview:
Consider using a different, more efficient data structure, such as a Binary Search Tree. These are more efficient and pretty easy to implement once you learn the concepts behind them. They give O(logN) search times where N = number of entries in the tree.
Topic archived. No new replies allowed.