2
votes
1answer
95 views

How to know, with good performance, which areas a certain point is in? [duplicate]

I'm interested in build a prototype that needs this sort of thing: Point A (xa, ya) with a radius of 500 meters. Point B (xb, yb) with a radius of 700 meters. Point C (xc, yc) with a radius of 1200 ...
1
vote
2answers
193 views

How fast should a Python factoring script be?

Just how efficient is "good enough" for all intents and purposes? I wrote a script to simply list off all numbers that divide into an input, x, as pairs (i, n//i) and was just curious how efficient I ...
5
votes
2answers
290 views

Structuring Access Control In Hierarchical Object Graph

I have a Folder entity that can be Moderated by users. Folders can contain other folders. So I may have a structure like this: Folder 1 Folder 2 Folder 3 Folder 4 I have to ...
0
votes
0answers
71 views

Efficient Copy While Sorting

I have an algorithms library called NDex. I am in the process of upgrading it to a new version. Part of this upgrade involves providing two versions of many algorithms: an in-place version and a ...
0
votes
2answers
833 views

How to find local maxima in matrices?

I need to develop an algorithm for finding all the local maxima in a two-dimensional array: how to search for local maxima in the the most efficient way? Are there algorithms about it? Moreover, the ...
6
votes
3answers
652 views

A question regarding linked list vs vector insert/remove results comparison

I was reading this blog post: http://kjellkod.wordpress.com/2012/02/25/why-you-should-never-ever-ever-use-linked-list-in-your-code-again/ and I found there a code to run: http://ideone.com/62Emz ...
1
vote
1answer
255 views

Effective implementation of “array” of type Int X String -> String in .NET or in general

The question in general is: is there a more effective way of implementation of table with structure like Dictionary<int, Dictionary<string, string>>? The reason I am asking this is ...
6
votes
2answers
367 views

Versioned Resources to Improve Cacheability

Here's an API concept which could be useful for performance optimisation. It's an example of key-based cache expiry applied to a broader internet-wide context instead of the internal Memcached-style ...
8
votes
1answer
351 views

Is there any better approach to shortest path finding within a (vehicular) traffic network?

Dear fellow programmers, We're developing software which simulates vehicular traffic. Part of the process called "assignment" is concerned with assigning vehicles to their routes and has to use some ...
8
votes
2answers
2k views

What does it mean by expected running time and average runnnig time of an algorithm?

Let's say we want to analyze running time of algorithms. Sometimes we say that we want to find the running time of an algorithm when the input size is n and for the worst possible case it is denote it ...
7
votes
4answers
2k views

Improving grepping over a huge file performance

I have FILE_A which has over 300K lines and FILE_B which has over 30M lines. I created a bash script that greps each line in FILE_A over in FILE_B and writes the result of the grep to a new file. ...
20
votes
6answers
13k views

Why is quicksort better than other sorting algorithms in practice?

This is a repost of a question on cs.SE by Janoma. Full credits and spoils to him or cs.SE. In a standard algorithms course we are taught that quicksort is O(n log n) on average and O(n²) in the ...
1
vote
6answers
6k views

Merge sort versus quick sort performance

I have implemented merge sort and quick sort using C (GCC 4.4.3 on Ubuntu 10.04 running on a 4 GB RAM laptop with an Intel DUO CPU at 2GHz) and I wanted to compare the performance of the two ...
3
votes
1answer
3k views

Magic square check for N×N matrix with minimum complexity

Is there any algorithm that works better than O(n²) to verify whether a square matrix is a magic one (e.g. such as sum of all the rows, cols and diagonally are equal to each other)? I did see someone ...
3
votes
5answers
1k views

Structuring database for multi-object “activity” and “following” functionalities

I am working on a web application which operate with different types of objects such as user, profiles, pages etc. All objects have unique object_id. When objects interact it may produce "activity", ...
4
votes
1answer
279 views

Inexpensive generation of hierarchical unique IDs

My application is building a hierarchical structure like this: root = { 'id': 'root', 'children': [ { 'name': 'root_foo', 'children': [] }, { 'id': 'root_foo2', 'children': [ { ...
11
votes
6answers
555 views

Examples of general purpose algorithms that have benefited from running on a GPU?

I am looking for examples of general purpose algorithms (meaning non-graphics related) that have been proven to run an order of magnitude faster on a GPU than on a CPU. I will use these examples to ...
4
votes
2answers
2k views

InterviewStreet (Vertical Sticks) just a tip where to get started

Having a lot of trouble with this question in interviewstreet.com: Given array of integers Y=y1,...,yn, we have n line segments such that endpoints of segment i are (i, 0) and (i, yi). Imagine that ...
0
votes
2answers
205 views

Algorithm for searching the neighbors neighbor of a directed graph

Is there an algorithm to search a directed graph (tree) for its neighbors neighbor? My current brute-force solution works as follows: for each node n: for each child c of n for each parent ...
5
votes
4answers
2k views

Big-O for nested loop

I am reading this post on Big-O It says that the following code is O(n^2): bool ContainsDuplicates(String[] strings) { for(int i = 0; i < strings.Length; i++) { for(int j = 0; j ...
2
votes
6answers
241 views

Complexity vs maintainability in modern hardware

Today with the modern hardware and memory coming cheap, how much sense does it make to spend effort to analyze algoriths or data structure complexity? Wouldn't it be better instead, to focus on clean, ...
2
votes
2answers
2k views

Best resources to really understand run-time complexity

I'm familiar with the basics of run-time analysis such as what makes certain types of code O(n) and O(n^2). But I'm having real trouble learning, understanding, and really remembering how to analyze ...
8
votes
3answers
888 views

What is the best way to keep track of the median?

I read a question in one book: Numbers are randomly generated and stored into an (expanding) array, How would you keep track of the median? There are two data structures can solve the problem. One is ...
3
votes
3answers
249 views

Improve address lookup usability and accuracy?

In my application,I have a feature like this: The user wants to add a new address to the database. Before adding the address, he needs to perform a search(using input parameters like ...
3
votes
3answers
211 views

How to query a very long list of properties fast

I have a structure for storing item properties on SQL Server: ItemId PropertyId Value 1 1 a 1 2 b 2 1 a 2 2 5 Currently there are over 130000 ...