Line Segments: Test Data. Post your results.
I've attached my test (1MB) input file.
The process of generation is following. There are 3 input parameters: count, length, and limit. count is the number of line segments, length is the maximum length of a segment in each dimention, and limit determines range of values for coordinates. Here is piece of code:
int coord [6];
for (int n = 0; n != count; n += 1)
{
for (int j = 0; j != 3; j += 1)
coord[j] = (int)(rand_gen() * limit);
for (int j = 0; j != 3; j += 1)
coord[j + 3] = coord[j] + (int)(rand_gen() * length * 2) - length;
fprintf(f, "%s %d %d %d %d %d %dn", name, coord[0], coord[1], coord[2], coord[3], coord[4], coord[5]);
}
Parameters for attached file are: count = 100'000, limit = 200, length = 20.
---------------------------------------------
All about lock-free algorithms, multicore, scalability, parallel computing and related topics:
www.1024cores.net | |
Re: Line Segments: Test Data. Post your results.
My program has found 1622 intersections in 21 sec.
However I am not 100% sure in correctness of my program now. Since it's difficult to manually compare output of one program with output of another program, I propose following method for quick verification/comparison of results.
The idea is to compute some "hash" of results. Hash must be stable to following reorderings:
A B
C D
must yield the same hash as:
D C
B A
But not stable to following reorderings:
A B
C D
must not yield the same hash as:
A C
B D
Here is algorithm I currently use:
char hash [4] = {};
for (size_t i = 0; i != results.size(); i += 1)
{
line_t const* line1 = results[i].line1;
line_t const* line2 = results[i].line2;
for (int t = 0; t != 4; t += 1)
hash[t] ^= (line1->name[t] + line2->name[t]);
}
}
printf("count=%u (%u)n", results.size(), *(unsigned*)sample);
My output is:
count=1622 (1711155)
---------------------------------------------
All about lock-free algorithms, multicore, scalability, parallel computing and related topics:
www.1024cores.net | |
Re: Line Segments: Test Data. Post your results.
However I am not 100% sure in correctness of my program now. Since it's difficult to manually compare output of one program with output of another program, I propose following method for quick verification/comparison of results.
The idea is to compute some "hash" of results....
Another approach is to run the output through sort and then compare the sorted outputs.
| |
Re: Line Segments: Test Data. Post your results.
hi Dmitriy Vyukov
My program has found 5352 intersections in 6 sec.
写字楼里写字间,写字间里程序员
程序人员写程序,又拿程序换酒钱
酒醒只在网上坐,酒醉还来网下眠
酒醉酒醒日复日,网上网下年复年 | |
Re: Line Segments: Test Data. Post your results.
Simple optimization reduced time to 6247ms.
My brute force implementation says there are 4788 intersections...
| |
Re: Line Segments: Test Data. Post your results.
Another approach is to run the output through sort and then compare the sorted outputs.
Well, this will definitely produce better results, however one will have to attach own results and download others results, then pass them through some utility, and somebody has to develop that utility first...
What I would prefer is something much more "lightweight". Probably good variant will be to sort results and then calculate SHA1.
---------------------------------------------
All about lock-free algorithms, multicore, scalability, parallel computing and related topics:
www.1024cores.net | |
Re: Line Segments: Test Data. Post your results.
Can you post your results please? I want to verify visually whether I've missed any intersections. I'll let you know what I find out. Here's mine (linux)...
Thanks.
| |
Re: Line Segments: Test Data. Post your results.
My program has found 1622 intersections in 21 sec.
Quoting - akki
My brute force implementation says there are 4788 intersections...
My program has found 5352 intersections in 6 sec.
Cool! I like this :)
For knapsack it was easier, if you have higher value and your solution is feasible then you are on the safe side. For line segments it's unclear which solution is "more right".
My first attempt also yield some 4 thousands intersections, however then I re-implement it more carefully and it yield only 1622. It's not to say that my answer is correct, I am totally unsure that it is correct.
I would be nice if somebody will construct input file with several tens of different corner cases and manually calculate correct answer... AMD Threadfest was much contestant-friendlier in this aspect - they initially provide a number of input datasets, pre-calculated correct results, simple reference implementation of the program and precisely describe input data generation process, so that contestants was able to concentrate on the problem itself...
---------------------------------------------
All about lock-free algorithms, multicore, scalability, parallel computing and related topics:
www.1024cores.net | | |
