|
A few years ago, I wrote a Skip List[^] class in C#. I've found this data structure to be handy. For one thing, it's easily adapted to a priority queue[^].
What I'd like to do is add the ability to access items in the skip list by index, e.g. give me the n'th item in the list. This is easy enough to do in O(N) time by simply starting at the beginning of the list and moving one by one through the list until you've reached the desired item. I was looking for a better way. Kunth decribes a way to do this with binary search trees. I'd like to find the equivalent algorithm for skip lists.
William Pugh, the skip list's inventor, decribes a way in his skip list cookbook[^]. But his algorithm assumes the existance of a "distance" field in each node. The distance field represents the next nodes position minus the current nodes position.
I didn't find this very helpful. It requires each node and each pointer level to know their position in the list. Well, if they know that already, then it's easy enough to search for the specified item by position to begin with.
It would be easy enough to add a position field to each node. The position would represent the node's index into the list. The problem becomes trying to maintain this field as items are added and removed from the list. Descructive operations will make the position value of all subsequent nodes invalid.
This may be a problem where there isn't a solution, at least not one that works as well as the binary search tree approach. Anyway, I'd appreciate any insights.
|
|
|
|
|
Hi,
I think the distance field is the right way to go; you can fill it while populating
the skip list at very modest cost. And its update needs are limited, whereas an
absolute index field would require expensive updating when new nodes get added.
|
|
|
|
|
Well, I'm embarrassed to say it, but I just noticed the "InsertByPosition" algorithm at the end of William Pugh's cookbook paper; I hadn't looked at it when I made my original post. Looks like the algorithm for managing the distance field is right there.
|
|
|
|
|
|
I am impressed.
I kinda wish i wasn't... but i am...
|
|
|
|
|
Guys I'm very stuck.I've searched the web for the past three weeks for a class written in C# that has low pass, high pass, Band pass filters which I could used for my third year project data analysis. I'm very desperate and my eyes are bloody red right now due to lack sleep; please help...
I believe there are alot of geniuses in this forum who cannot be stopped by anything..Looking forward to receiving your help...
Cheers
kel
|
|
|
|
|
Write your own! I did when I was in college, though we didn't have fancy languages like C#. It took all of a few hours and was a great learning tool (for filter theory, not programming).
"A Journey of a Thousand Rest Stops Begins with a Single Movement"
|
|
|
|
|
I was going to make the same comment. It is after all a project on data analysis. It shouldn't take too long to write some basic filters. Get some basic filtering routines going, initially use matlab or similar to calculate the coefficients, work up to doing your own. If you are stuck, look at some of the c++ signal processing libraries - the code should be similar.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Hi all,
I have a set of integers like 3,7,4,15,... and
the problem to find is how can we find a subset
with atleaset M (>=3) intergers in it and the total
of those intergers equals to the given N
thanks in advance
========================
sorry for my english and i code in c/c++
|
|
|
|
|
What's this - an easter craze on knapsack problems?
This looks like homework, in which case I guess the number of integers in the set is modest (<= say 16), in which case you can simply search all combinations and find the best.
For other comments and a more general solution see this thread: link[^]
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
please tell me if there is any way to convert an array like 936 to an integer 936?
and how can i understand that the number the user inputs how many digits has?(for example 99999 is a 5digit number)
Khodadad Pakdaman
Pakdaman@CleanMail.it
|
|
|
|
|
array ?
if you mean string, use int.Parse() or int.TryParse()
if you mean a char array, first convert it to a string using a String constructor.
|
|
|
|
|
My suggestion for a beginner like yourself is to find a tutorial in whatever language you are using, one with some simple examples involving user i/o, get these working and then experiment with modifying them to do what you want.
Google on (language of choice) tutorial
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
if you are able to write this program please help me:
YOU KNOW THAT THE ISDN NUMBER IS A SPECIFIC NUMBER FOR EACH BOOK,AND FOR EXAMPLE AN ISDN NUMBER LIKE 964-92032-1-4 CONTAINS THIS INFORMATION:
ISDN : TheLanguageOfTheBook-PublisherCode-BookNumber-CheckDigit
the check digit number is calculated in this way,
for example for 964-92032-1-4 :
10x9 + 9x6 + 8x4 + 7x9 + 6x2 + 5x0 + 4x3 + 3x2 + 2x1 = 271
271%11=7 = Result
then the CheckDigit number should be (11-Result)
ok?
Here's the interface of the program:
Enter ISBN: 964-92032-1-4
Language: 964
Publisher: 92032
Book number: 1
Check digit: 4
This ISBN code “964-92032-1-4” is valid!
or
This ISBN code “964-92032-1-4” is invalid!
Please let me know if you understood the program well!thanks again,sorry for the english mistakes found in my text,i'm really sorry!
Khodadad Pakdaman
Pakdaman@CleanMail.it
|
|
|
|
|
Sounds like homework to me - in which case try to do it and if you run into difficulties post on one of the programming forums.
Just noticed that you have posted the same question on the Managed C++ forum. This is a BIG hint - you will get much more help here if you are seen to be making an effort yourself. If you just type your problem into the forum expecting someone else to do your work, you will not get much of a response.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
ok,dear peter,
thanks for your reccomendations,
in a simple C++ program,
please tell me if there is any way to convert an array like 936 to an integer 936?
and how can i understand that the number the user inputs how many digits has?(for example 99999 is a 5digit number)
in the case mentioned up there,i don't know how i can calculate the check digit number?because i stored the input in a string!
Thanks again for your reccomendations,
Khodadad Pakdaman,
Pakdaman@CleanMail.it
|
|
|
|
|
How about the standard C function "strtoul()" which stands for "string to unsigned long". Will that do it for you?
|
|
|
|
|
Hey. I am doing advanced maths this year and need help with quadratics.
The chapter that I am doing focuses on find a quadratic rule from a given graph or co-ordinates.
The book I am using is state approved, but does not seem to explain what to do.
My question is, can anyone make a "guide" on what to do for different scenarios.
For example, what should I do when I know one co-ordinate or when I know two co-ordinates etc.
And also, what is the quadratic rule if a graph has vertex (-1,3) and passes through (3,8)?
Thanks in advance
|
|
|
|
|
I don't think this is the place for school maths homework. Some hints:
1. read the book again
2. hopefully discover that the 'quadratic rule' is commonly called the parabola
3. google on thinge like {parabola vertex} etc
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Thanks for the advice.
The book did not help but I found a very good tutorial on the net. Now I can find the rule for a set of given points
Thanks again
|
|
|
|
|
pHysiX wrote: The book did not help but I found a very good tutorial on the net.
It would be very helpful to others trying to figure out how to solve this type of problem if you posted a link to the tutorial that you found.
Thanks,
BillW
|
|
|
|
|
I am trying to find a solution/algorithm which can find a closest match to a given number. For example you were given 100 and you have 10 records in a table in following order:
1. 28
2. 35
3. 43
4. 23
5. 35
6. 78
7. 8
8. 5
9. 12
10. 33
I need to find sum of what combination of these records matches close or equal to 100 (but it should not exceed). One record can be used only one time. I am looking for an algorithm which can find the combination quickly. In this example I have only 10 records to search. But there can be more records. Number of records to search increases regular way of checking combinations takes more time. I really appreciate if anyone can provide me an algorithm which can do this type of job quickly.
Thanks in advance
Sam
|
|
|
|
|
Hi,
this seems like an extension to the "knapsack problem" (fill a given space with as
many objects as possible from a given collection); I suggest you google it.
|
|
|
|
|
What if you first sorted the set of numbers, yielding:
{78, 43, 35, 35, 33, 28, 23, 12, 8, 5}
Then search the set for the largest number that is less than or equal to 100, subtract that from 100, search the set again for the largest number that is less than or equal to 22, subtract that from 22, etc. So, 78+12+8 is the closest you can get to 100.
Or am I way off base?
"Approved Workmen Are Not Ashamed" - 2 Timothy 2:15
"Judge not by the eye but by the heart." - Native American Proverb
|
|
|
|
|
No you're not. What you could do is add the largest to the smallest and save it subtract 100 and save it. Stop if 0. Then use the second smallest and compare to the last result. Save the smaller one. If it becomes negative, change the largest number and keep the current smallest number. Repeat until you get two numbers that sum to less than 100 and your previous pair are the answer you're looking for.
"Oh, what a tangled web we weave, when first we practice to deceive." - Sir Walter Scott
Web - Blog - RSS - Math - LinkedIn - BM
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
