473,387 Members | 1,492 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,387 software developers and data experts.

at_most: search "dictionary" for less than or equal

Before I set out to reinvent the wheel.

I want a dictionary-like structure for which most lookups will be on a
key that is not in the "dictionary"; in which case I want a key/value
returned which is the closest key that is less than the search term.
The batch solution of matching the values in two sorted sequences is
efficient but a random lookup would be more convenient. A solution based
on AVL trees seems possible.
--
djc
Aug 11 '08 #1
2 1423
slais-www, a BK-tree maybe isn't right what you need but it may be
enough:
http://code.activestate.com/recipes/572156/

Bye,
bearophile
Aug 11 '08 #2
On Aug 11, 9:18 am, slais-www <slais-...@ucl.ac.ukwrote:
Before I set out to reinvent the wheel.

I want a dictionary-like structure for which most lookups will be on a
key that is not in the "dictionary"; in which case I want a key/value
returned which is the closest key that is less than the search term.

The batch solution of matching the values in two sorted sequences is
efficient but a random lookup would be more convenient. A solution based
on AVL trees seems possible.

--
djc
Sounds like you have very long lists to work with. Maybe a solution
using bisect would combine simplest structure with best performance.

-- Paul
Aug 11 '08 #3

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

Similar topics

16
by: Dave Opstad | last post by:
In this snippet: d = {'x': 1} value = d.get('x', bigscaryfunction()) the bigscaryfunction is always called, even though 'x' is a valid key. Is there a "short-circuit" version of get that...
2
by: microsoft | last post by:
When I create a instance of web services proxy in winform, I get the exception. Stack Trace: System.ArgumentException: Item has already been added. Key in dictionary:"winbootdir" Key being...
2
by: Kenneth D Buelow | last post by:
Is there a way to generate a listing of some/all of the "field descriptors" for an ACCESS table? I am a SAS user and am looking for something like SAS's proc CONTENTS which generates a basic "data...
21
by: Helge Jensen | last post by:
I've got some data that has Set structure, that is membership, insert and delete is fast (O(1), hashing). I can't find a System.Collections interface that matches the operations naturally offered...
1
by: Scott Starker | last post by:
Hi all. I'm a newbie and I am reading "Programming in the Key of C#" by Charles Petzold. I am getting an idea of how C# works and writing a "Hangman" program just for the fun it. But, I am in...
0
by: Ralf Gedrat | last post by:
Hello! I have a Application, this throws after some time following exception: Item has already been added. Key in dictionary: "- 1" key being added: "- 1" I use Application.Run with...
1
by: nobrainer | last post by:
Hi, I'm a linguist and have a large self-built bilingual dictionary. I want to turn it into a electronic dictionary, can anyone tell me how to start with it? I've some knowledge in Java...
2
by: joe.kimbler | last post by:
What is the best way to handle updates in databases with each release of a software package? I used to work on an accounting package in FoxPro that had a "Data Dictionary" and as your code...
0
by: =?Utf-8?B?S2V2aW4gU2NobmVpZGVy?= | last post by:
I have two projects (one using .NET 1.1 the other using 2.0). When I call a particular method in a webservice from the 1.1 project everything works great. When I call the same method from the 2.0...
0
by: taylorcarr | last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: aa123db | last post by:
Variable and constants Use var or let for variables and const fror constants. Var foo ='bar'; Let foo ='bar';const baz ='bar'; Functions function $name$ ($parameters$) { } ...
0
by: ryjfgjl | last post by:
If we have dozens or hundreds of excel to import into the database, if we use the excel import function provided by database editors such as navicat, it will be extremely tedious and time-consuming...
0
by: ryjfgjl | last post by:
In our work, we often receive Excel tables with data in the same format. If we want to analyze these data, it can be difficult to analyze them because the data is spread across multiple Excel files...
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
1
by: nemocccc | last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
0
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However,...
0
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...

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.