strstr(s1,s2)是一个经常用的函数，他的作用就是在字符串s1中寻找字符串s2如果找到了就返回指针，否则返回NULL。下面是这个函数的一个简单实现：
static const char* _strstr(const char* s1, const char* s2)
{
assert(s2 && s1);
if(S1 == '\0') return NULL;
const char* p=s1, *r=s2;
while(*p!='\0')
{
while(*p++==*r++ && *p!='\0' && *r!='\0');
if(*r=='\0')
return s1;
if(*p=='\0')
return NULL;
r=s2;
p=++s1;
}
return NULL;
}
Computer science literature is packed full of sorting algorithms, and all of them seem to operate on arrays. Everybody knows the Sorting Facts Of Life:
O(N log N) limit; O(N) auxiliary space; Nobody tells you what to do if you want to sort something other than an array. Binary trees and their ilk are all ready-sorted, but what about linked lists?
It turns out that Mergesort works even better on linked lists than it does on arrays. It avoids the need for the auxiliary space, and becomes a simple, reliably O(N log N) sorting algorithm. And as an added bonus, it's stable too.
Mergesort takes the input list and treats it as a collection of small sorted lists. It makes log N passes along the list, and in each pass it combines each adjacent pair of small sorted lists into one larger sorted list. When a pass only needs to do this once, the whole output list must be sorted.
So here's the algorithm. In each pass, we are merging lists of size K into lists of size 2K. (Initially K equals 1.) So we start by pointing a temporary pointer p at the head of the list, and also preparing an empty list L which we will add elements to the end of as we finish dealing with them. Then:
p is null, terminate this pass. K lists, so increment the number of merges performed in this pass. q, at the same place as p. Step q along the list by K places, or until the end of the list, whichever comes first. Let psize be the number of elements you managed to step q past. qsize equal K. Now we need to merge a list starting at p, of length psize, with a list starting at q of length at most qsize. psize > 0) or the q-list is non-empty (qsize > 0 and q points to something non-null): e, from the start of its list, by advancing p or q to the next element along, and decrementing psize or qsize. e to the end of the list L we are building up. p until it is where q started out, and we have advanced q until it is pointing at the next pair of length-K lists to merge. So set p to the value of q, and go back to the start of this loop. As soon as a pass like this is performed and only needs to do one merge, the algorithm terminates, and the output list L is sorted. Otherwise, double the value of K, and go back to the beginning.
This procedure only uses forward links, so it doesn't need a doubly linked list. If it does have to deal with a doubly linked list, the only place this matters is when adding another item to L.
Dealing with a circularly linked list is also possible. You just have to be careful when stepping along the list. To deal with the ambiguity between p==head meaning you've just stepped off the end of the list, and p==head meaning you've only just started, I usually use an alternative form of the "step" operation: first step p to its successor element, and then reset it to null if that step made it become equal to the head of the list.
(You can quickly de-circularise a linked list by finding the second element, and then breaking the link to it from the first, but this moves the whole list round by one before the sorting process. This wouldn't matter - we are about to sort the list, after all - except that it makes the sort unstable.)
Like any self-respecting sort algorithm, this has running time O(N log N). Because this is Mergesort, the worst-case running time is still O(N log N); there are no pathological cases.
Auxiliary storage requirement is small and constant (i.e. a few variables within the sorting routine). Thanks to the inherently different behaviour of linked lists from arrays, this Mergesort implementation avoids the O(N) auxiliary storage cost normally associated with the algorithm.
Any situation where you need to sort a linked list.
Sample code in C is provided here.
Problem Statement
source: http://gregable.com/2007/10/reservoir-sampling.html
Now that that is out of the way, Reservoir Sampling is a fun algorithm. Imagine you are given a really large stream of data elements (queries on Google searches in May, products bought at Walmart during the Christmas season, names in a phone book, whatever). Your goal is to efficiently return a random sample of 1,000 elements evenly distributed from the original stream. How would you do it?
The right answer is generating random integers between 0 and N-1, then retrieving the elements at those indices and you have your answer.
So, let me make the problem harder. You don't know N (the size of the stream) in advance and you can't index directly into it !!!!!!!!. You can count it, but that requires making 2 passes of the data. You can do better. There are some heuristics you might try: guess the length and hope to undershoot. It will either not work in one pass or not be evenly distributed.
Simple Solution
A relatively easy and correct solution is to assign a random number to every element as you see them in the stream, and then always keep the top 1,000 numbered elements at all times. This is similar to how mysql does "ORDER BY RAND()" calls.
tu: what is the problem with this simple solution??????????????
A: simpler in this problem, but cannot be extended to the more complex cases, which we will see later.
Classic Reservoir Sampling
Another option is reservoir sampling. In the example I've given you, the algorithm above is a little simpler, but reservoir sampling can be extended in other ways which I will get to, but first the basic algorithm:
First, you want to make a reservoir (array) of 1,000 elements and fill it with the first 1,000 elements in your stream. That way if you have exactly 1,000 elements, the algorithm works. This is the base case.
Next, you want to process the i'th element (starting with i = 1,001) such that at the end of processing that step, the 1,000 elements in your reservoir are randomly sampled amongst the i elements you've seen so far. How can you do this. Start with i = 1,001. With what probability after the 1001'th step should element 1,001 (or any element for that matter) be in the set of 1,000 elements? The answer is easy: 1,000/1,001. So, generate a random number between 0 and 1, and if it is less than 1,000/1,001 you should take element 1,001. In other words, choose to add element 1,001 to your reservoir with probability 1,000/1,001. If you choose to add it (which you likely will), then replace any element in the reservoir chosen randomly. I've shown that this produces a 1,000/1,001 chance of selecting the 1,001'th element, but what about the 2nd element? The second element is definitely in the reservoir at step 1,000 and the probability of it getting removed is the probability of element 1,001 getting selected multiplied by the probability of #2 getting randomly chosen as the replacement candidate. That probability is 1,000/1,001 * 1/1,000 = 1/1,001. So, the probability that #2 survives this round is 1 - that or 1,000/1,001.
This can be extended for the i'th round - keep the i'th element with probability 1,000/i and if you choose to keep it, replace a random element from the reservoir. It is pretty easy to prove that this works for all values of i using induction. It obviously works for the i'th element based on the way the algorithm selects the i'th element with the correct probability outright. The probability any element before this step being in the reservoir is 1,000/(i-1). The probability that they are removed is 1,000/i * 1/1,000 = 1/i. The probability that each element sticks around given that they are already in the reservoir is (i-1)/i and thus the elements' overall probability of being in the reservoir after i rounds is 1,000/(i-1) * (i-1)/i = 1,000/i.
Weighted Reservoir Sampling Variation
tu: seems not quite right. What is the reservoir size?
Take the same problem above but add the extra challenge: How would you sample from a weighted distribution where each element is given a weight? This is sorta tricky. The above algorithm can be found on the web easily, but I don't know where I can find a weighted reservoir sampling version, so I made one up. I'm 100% sure someone has figured this out before me though, I don't take credit.
Start the same way by filling in the first 1,000 elements of the reservoir except keep a sum of the weights seen so far. Call this seen_weight. Also, make sure to store the weights of the individual elements stored in the reservoir. Call these weights a different array named weight[]. Lastly, to keep things efficient, store a variable for the total weight of the elements in the reservoir called reservoir_weight. On step i, generate a random number between 0 and 1 and use this pseudocode:prob_sum = 0;
for(x = 0; x < (1-(weight[x]*seen_weight/reservoir_weight/(seen_weight + input_weight))))/reservoir_size; ++x) {
if (prob_sum > R) {
// replace, the probability of replace is input_weight/(seen_weight+inputweight)
reservoir[x] = input_element;
reservoir_weight += input_weight - weight[x];
weight[x] = input_weight;
break;
}
seen_weight += input_weight
}
The only magic here is: (1-(weight[x] * seen_weight / reservoir_weight / (seen_weight + input_weight))))/reservoir
Distributed Reservoir Sampling Variation
This is the problem that got me looking at the weighted sample above. In both of the above algorithms, I can process the stream in O(N) time where N is length of the stream, in other words: in a single pass. If I want to break break up the problem on say 10 machines and solve it close to 10 times faster, how can I do that?
The answer is to have each of the 10 machines take roughly 1/10th of the input to process and generate their own reservoir sample from their subset of the data. Then, a final process must take the 10 output reservoirs and merge them with another sample. The trick is that the final process must take into account the reservoir weights of each of the input reservoirs. Basically, the final process should reservoir sample every element in the 10 input reservoirs but assign each element a weight of weight[x] * seen_weight / reservoir_weight where weight[x] is the element's original weight, seen_weight is the total weight counted in generating that particular reservoir and reservoir_weight is the sum of the weights of the elements in the reservoir. Proving this works is a little harder, so I will frustrate you by leaving it as an excercise for the dear reader.
http://www.bearcave.com/software/java/wavelets/daubechies/index.html
I recommend using the "save as" feature of your browser to save the C++ and Java source files (I'm not sure how to reliably suppress viewing and force download with all browsers).
The Daubechies D4 algorithm as a C++ class
Doxygen generated documentation for the C++ version of the Daubechies D4 algorithm. This documentation was generated with this Doxygen configuration file.
The Daubechies D4 algorithm as a Java class
I have to confess up front that the comment here does not even come close to describing wavelet algorithms and the Daubechies D4 algorithm in particular. I don't think that it can be described in anything less than a journal article or perhaps a book. I even have to apologize for the notation I use to describe the algorithm, which is barely adequate. But explaining the correct notation would take a fair amount of space as well. This comment really represents some notes that I wrote up as I implemented the code. If you are unfamiliar with wavelets I suggest that you look at the bearcave.com web pages and at the wavelet literature. I have yet to see a really good reference on wavelets for the software developer. The best book I can recommend is Ripples in Mathematics by Jensen and Cour-Harbo.
All wavelet algorithms have two components, a wavelet function and a scaling function. These are sometime also referred to as high pass and low pass filters respectively.
The wavelet function is passed two or more samples and calculates a wavelet coefficient. In the case of the Haar wavelet this is
coefi = oddi - eveni
or
coefi = 0.5 * (oddi - eveni)
depending on the version of the Haar algorithm used.
The scaling function produces a smoother version of the original data. In the case of the Haar wavelet algorithm this is an average of two adjacent elements.
The Daubechies D4 wavelet algorithm also has a wavelet and a scaling function. The coefficients for the scaling function are denoted as hi and the wavelet coefficients are gi.
Mathematicians like to talk about wavelets in terms of a wavelet algorithm applied to an infinite data set. In this case one step of the forward transform can be expressed as the infinite matrix of wavelet coefficients represented below multiplied by the infinite signal vector.
ai = ...h0,h1,h2,h3, 0, 0, 0, 0, 0, 0, 0, ... si
ci = ...g0,g1,g2,g3, 0, 0, 0, 0, 0, 0, 0, ... si+1
ai+1 = ...0, 0, h0,h1,h2,h3, 0, 0, 0, 0, 0, ... si+2
ci+1 = ...0, 0, g0,g1,g2,g3, 0, 0, 0, 0, 0, ... si+3
ai+2 = ...0, 0, 0, 0, h0,h1,h2,h3, 0, 0, 0, ... si+4
ci+2 = ...0, 0, 0, 0, g0,g1,g2,g3, 0, 0, 0, ... si+5
ai+3 = ...0, 0, 0, 0, 0, 0, h0,h1,h2,h3, 0, ... si+6
ci+3 = ...0, 0, 0, 0, 0, 0, g0,g1,g2,g3, 0, ... si+7
The dot product (inner product) of the infinite vector and a row of the matrix produces either a smoother version of the signal (ai) or a wavelet coefficient (ci).
In an ordered wavelet transform, the smoothed (ai) are stored in the first half of an n element array region. The wavelet coefficients (ci) are stored in the second half the n element region. The algorithm is recursive. The smoothed values become the input to the next step.
The transpose of the forward transform matrix above is used to calculate an inverse transform step. Here the dot product is formed from the result of the forward transform and an inverse transform matrix row.
si = ...h2,g2,h0,g0, 0, 0, 0, 0, 0, 0, 0, ... ai
si+1 = ...h3,g3,h1,g1, 0, 0, 0, 0, 0, 0, 0, ... ci
si+2 = ...0, 0, h2,g2,h0,g0, 0, 0, 0, 0, 0, ... ai+1
si+3 = ...0, 0, h3,g3,h1,g1, 0, 0, 0, 0, 0, ... ci+1
si+4 = ...0, 0, 0, 0, h2,g2,h0,g0, 0, 0, 0, ... ai+2
si+5 = ...0, 0, 0, 0, h3,g3,h1,g1, 0, 0, 0, ... ci+2
si+6 = ...0, 0, 0, 0, 0, 0, h2,g2,h0,g0, 0, ... ai+3
si+7 = ...0, 0, 0, 0, 0, 0, h3,g3,h1,g1, 0, ... ci+3
Using a standard dot product is grossly inefficient since most of the operands are zero. In practice the wavelet coefficient values are moved along the signal vector and a four element dot product is calculated. Expressed in terms of arrays, for the forward transform this would be:
ai = s[i]*h0 + s[i+1]*h1 + s[i+2]*h2 + s[i+3]*h3
ci = s[i]*g0 + s[i+1]*g1 + s[i+2]*g2 + s[i+3]*g3
This works fine if we have an infinite data set, since we don't have to worry about shifting the coefficients "off the end" of the signal.
I sometimes joke that I left my infinite data set in my other bear suit. The only problem with the algorithm described so far is that we don't have an infinite signal. The signal is finite. In fact not only must the signal be finite, but it must have a power of two number of elements.
If i=N-1, the i+2 and i+3 elements will be beyond the end of the array. There are a number of methods for handling the wavelet edge problem. This version of the algorithm acts like the data is periodic, where the data at the start of the signal wraps around to the end.
This algorithm uses a temporary array. A Lifting Scheme version of the Daubechies D4 algorithm does not require a temporary. The matrix discussion above is based on material from Ripples in Mathematics, by Jensen and Cour-Harbo. Any error are mine.
Author: Ian Kaplan
Use: You may use this software for any purpose as long as I cannot be held liable for the result. Please credit me with authorship if use use this source code.
This comment is formatted for the doxygen documentation generator
perfect one!!!! contain many generators!!!
http://www.agner.org/random/
This page contains software libraries for some very good random number generators.
The basic random number generators make floating point or integer random numbers with uniform distributions. This code is available in C++ and assembly language.
The non-uniform random number generators make random variates with the following distributions:
normal, bernoulli, poisson, binomial, hypergeometric, Wallenius' and Fisher's noncentral hypergeometric, multinomial, multivariate hypergeometric, Wallenius' and Fisher's multivariate noncentral hypergeometric, and shuffling. This code is available in C++ language.
Code examples are included, showing how to use these software libraries.
The uniform random number generators are also available as ready-to-use library files which can be linked into projects in many different programming languages under Windows, Linux, BSD and other operating systems on the PC platform. These libraries are coded in assembly language for improved speed.
These generators are intended for Monte Carlo applications, not for cryptographic applications.
Comments to the theory of these random number generators can be posted to my discussion board.
Follow my research on the noncentral hypergeometric distributions.
Please don't mail me with your programming problems. Your mail will not be answered.
1. sources
#include
#include
using namespace std;
int main()
{
int random_integer = rand();
cout <<>
#include
#include
using namespace std;
int main()
{
cout << "The value of RAND_MAX is " <<>
#include
#include
#include
using namespace std;
int main()
{
srand((unsigned)time(0));
int random_integer = rand();
cout <<>
#include
#include
#include
using namespace std;
int main()
{
srand((unsigned)time(0));
int random_integer;
for(int index=0; index<20; random_integer =" (rand()%10)+1;">
#include
#include
#include
using namespace std;
int main()
{
srand((unsigned)time(0));
int random_integer;
int lowest=1, highest=10;
int range=(highest-lowest)+1;
for(int index=0; index<20; random_integer =" lowest+int(range*rand()/(RAND_MAX">
Name: kdtree
Author: Steven Michael (smichael@ll.mit.edu)
Date: 3/1/2005
############################################################
The following code implements a KDTree search algorithm
in MATLAB
There are 4 main functions:
1. kdtree -- tree class creation
2. kdtree_range -- return all points within a range
3. kdtree_closestpoint -- return array of closest points to a
corresponding array of input points
A single reference was used in writing the code:
M. deBerg, M. vanKreveld, M. Overmars, and O. Schwarzkopf.
"Computational Geometry: Algorithms and Applications"
Springer, 2000.
download