473,324 Members | 2,581 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,324 software developers and data experts.

Best algorithm...

Hi,

Need some ideas for this problem:

If you had a file containing boundaries [A,B] (up to 25 million) and a
file containing a list of points P (up to 10 billion). What would be
the fastest way to determine which of the listed boundaries contain a
point P?

Standard ugly std::count_if and map inserts and lookup are far to
slow for this problem. Any other ideas?

(problem is a simpler version of a derivative default map issue I'm
having)

Thanks for any help.
Feb 5 '08 #1
3 1531
Thanks for the info. I have also considered a binary tree, however I
forgot to mention a key point that might not work for a binary tree.

We need to determine all applicable boundary values for a specific
point. Eg. point 3 is contained within 2000 of the 25 million
boundaries specified.

A binary tree would imply multiple searches to find all applicable
boundaries. Or some trickery based on the depth of node on a tree.
Feb 5 '08 #2
On 5 Feb, 16:29, "ahmadcor...@googlemail.com"
<ahmadcor...@googlemail.comwrote:
Thanks for the info. I have also considered a binary tree, however I
forgot to mention a key point that might not work for a binary tree.

We need to determine all applicable boundary values for a specific
point. Eg. point 3 is contained within 2000 of the 25 million
boundaries specified.
After wiki-ing a while, I've found the following:

http://en.wikipedia.org/wiki/Interval_tree
http://en.wikipedia.org/wiki/Segment_tree

Phil's solution is very similar to "Alternative 1" in the first
article and I think it's the most appropriate for your problem.

Dario
Feb 6 '08 #3
On 6 Feb, 08:00, Dario Saccavino <kath...@gmail.comwrote:
On 5 Feb, 16:29, "ahmadcor...@googlemail.com"

<ahmadcor...@googlemail.comwrote:
Thanks for the info. I have also considered a binary tree, however I
forgot to mention a key point that might not work for a binary tree.
We need to determine all applicable boundary values for a specific
point. Eg. point 3 is contained within 2000 of the 25 million
boundaries specified.

After wiki-ing a while, I've found the following:

http://en.wikipedia.org/wiki/Interva...i/Segment_tree

Phil's solution is very similar to "Alternative 1" in the first
article and I think it's the most appropriate for your problem.

Dario
Thanks for the references. The algorithm is much clearer now. Thanks
to all. Immensely appreciate it.
Feb 6 '08 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
by: rdsteph | last post by:
I am having a lot of fun using the pyGoogle module ( http://pygoogle.sourceforge.net/ ) that uses the Google API. It is about as easy to use as I can imagine, and it is a lot nicer than using my...
3
by: PWalker | last post by:
Hi, I have written code that I would like to optimize. I need to push it to the limit interms of speed as the accuracy of results are proportional to runtime. First off, would anyone know any...
136
by: Matt Kruse | last post by:
http://www.JavascriptToolbox.com/bestpractices/ I started writing this up as a guide for some people who were looking for general tips on how to do things the 'right way' with Javascript. Their...
10
by: Kent | last post by:
Hi! I want to store data (of enemys in a game) as a linked list, each node will look something like the following: struct node { double x,y; // x and y position coordinates struct enemy...
12
by: nib | last post by:
What kind of problems is c best at solving?
8
by: robert | last post by:
Hello, I want to put (incrementally) changed/new files from a big file tree "directly,compressed and password-only-encrypted" to a remote backup server incrementally via FTP,SFTP or DAV.... At...
5
by: google | last post by:
Hi All, I'm just getting started learning to use <algorithm> instead of loads of little for loops, and I'm looking for a bit of advice/mentoring re: implementing the following... I have a...
9
by: raylopez99 | last post by:
What's the best way of implementing a multi-node tree in C++? What I'm trying to do is traverse a tree of possible chess moves given an intial position (at the root of the tree). Since every...
6
by: pj | last post by:
Hi, I 'm currently writing a program that performs transliteration (i.e., converts greek text written using the english alphabet to "pure" greek text using the greek alphabet) as part of my...
6
by: kamsmartx | last post by:
I'm new to programming and need some help figuring out an algorithm. I need to design some kind of algorithm which will help us define capacity for one of our portfolios....here's the problem...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.