Search Results

Search found 1848 results on 74 pages for 'algorithms'.

Page 17/74 | < Previous Page | 13 14 15 16 17 18 19 20 21 22 23 24  | Next Page >

• Even distribution through a chain of resources

  - by ClosetGeek

  I'm working on an algorithm which routes tasks through a chain of distributed resources based on a hash (or random number). For example, say you have 10 gateways into a service which distribute tasks to 1000 handlers through 100 queues. 10,000 connected clients are expected to be connected to gateways at any given time (numbers are very general to keep it simple). Thats 10,000 clients 10 gateways (producers) 100 queues 1000 workers/handlers (consumers) The flow of each task is client-gateway-queue-worker Each client will have it's own hash/number which is used to route each task from the client to the same worker each time, with each task going through the same gateway and queue each time. Yet the algorithm handles distribution evenly, meaning each gateway, queue, and worker will have an even workload. My question is what exactly would this be called? Does such a thing already exist? This started off as a DHT, but I realized that DHTs can't do exactly what I need, so I started from scratch.

  Read the article

• Looking for an algorithm to connect dots - shortest route

  - by e4ch

  I have written a program to solve a special puzzle, but now I'm kind of stuck at the following problem: I have about 3200 points/nodes/dots. Each of these points is connected to a few other points (usually 2-5, theoretical limit is 1-26). I have exactly one starting point and about 30 exit points (probably all of the exit points are connected to each other). Many of these 3200 points are probably not connected to neither start nor end point in any way, like a separate net, but all points are connected to at least one other point. I need to find the shortest number of hops to go from entry to exit. There is no distance between the points (unlike the road or train routing problem), just the number of hops counts. I need to find all solutions with the shortest number of hops, and not just one solution, but all. And potentially also solutions with one more hop etc. I expect to have a solution with about 30-50 hops to go from start to exit. I already tried: 1) randomly trying possibilities and just starting over when the count was bigger than a previous solution. I got first solution with 3500 hops, then it got down to about 97 after some minutes, but looking at the solutions I saw problems like unnecessary loops and stuff, so I tried to optimize a bit (like not going back where it came from etc.). More optimizations are possible, but this random thing doesn't find all best solutions or takes too long. 2) Recursively run through all ways from start (chess-problem-like) and breaking the try when it reached a previous point. This was looping at about a length of 120 nodes, so it tries chains that are (probably) by far too long. If we calculate 4 possibilities and 120 nodes, we're reaching 1.7E72 possibilities, which is not possible to calculate through. This is called Depth-first search (DFS) as I found out in the meantime. Maybe I should try Breadth-first search by adding some queue? The connections between the points are actually moves you can make in the game and the points are how the game looks like after you made the move. What would be the algorithm to use for this problem? I'm using C#.NET, but the language shouldn't matter.

  Read the article

• Improving python code

  - by cobie

  I just answered the question on project euler about finding circular primes below 1 million using python. My solution is below. I was able to reduce the running time of the solution from 9 seconds to about 3 seconds. I would like to see what else can be done to the code to reduce its running time further. This is strictly for educational purposes and for fun. import math import time def getPrimes(n): """returns set of all primes below n""" non_primes = [j for j in range(4, n, 2)] # 2 covers all even numbers for i in range(3, n, 2): non_primes.extend([j for j in range(i*2, n, i)]) return set([i for i in range(2, n)]) - set(non_primes) def getCircularPrimes(n): primes = getPrimes(n) is_circ = [] for prime in primes: prime_str = str(prime) iter_count = len(prime_str) - 1 rotated_num = [] while iter_count > 0: prime_str = prime_str[1:] + prime_str[:1] rotated_num.append(int(prime_str)) iter_count -= 1 if primes >= set(rotated_num): is_circ.append(prime) return len(is_circ)

  Read the article

• Algorithm for determining grid based on variably sized "blocks"?

  - by Lite Byte

  I'm trying to convert a set of "blocks" in to a grid-like layout. The blocks have a width of either 25%, 33%, 50%, 66%, or 75% of their container and each row of the grid should try to fit as many blocks as possible, up to a total width of 100%. I've discovered that trying to do this while leaving no remaining blocks in the original set is very hard. Eventually, I think my solution will be to upgrade/downgrade various block sizes (based on their priority or something) so they all fit in to a row. Either case, before I do that, I thought I'd check if someone has some code (or a paper) demonstrating a solution to this problem already? And bonus points if the solution incorporates varying block heights in to its calculations :) Thanks!

  Read the article

• Resolving equivalence relations

  - by Luca Cerone

  I am writing a function to label the connected component in an image (I know there are several libraries outside, I just wanted to play with the algorithm). To do this I label the connected regions with different labels and create an equivalence table that contain information on the labels belonging to the same connected component. As an example if my equivalence table (vector of vector) looks something like: 1: 1,3 2: 2,3 3: 1,2,3 4: 4 It means that in the image there are 2 different regions, one made of elements that are labelled 1,2,3 and an other made of elements labelled 4. What is an easy and efficient way to resolve the equivalences and end up with something that looks like: 1: 1,2,3 2: 4 that I can use to "merge" the different connected regions belonging to the same connected component? Thanks a lot for the help!

  Read the article

• Tiling Problem Solutions for Various Size "Dominoes"

  - by user67081

  I've got an interesting tiling problem, I have a large square image (size 128k so 131072 squares) with dimensons 256x512... I want to fill this image with certain grain types (a 1x1 tile, a 1x2 strip, a 2x1 strip, and 2x2 square) and have no overlap, no holes, and no extension past the image boundary. Given some probability for each of these grain types, a list of the number required to be placed is generated for each. Obviously an iterative/brute force method doesn't work well here if we just randomly place the pieces, instead a certain algorithm is required. 1) all 2x2 square grains are randomly placed until exhaustion. 2) 1x2 and 2x1 grains are randomly placed alternatively until exhaustion 3) the remaining 1x1 tiles are placed to fill in all holes. It turns out this algorithm works pretty well for some cases and has no problem filling the entire image, however as you might guess, increasing the probability (and thus number) of 1x2 and 2x1 grains eventually causes the placement to stall (since there are too many holes created by the strips and not all them can be placed). My approach to this solution has been as follows: 1) Create a mini-image of size 8x8 or 16x16. 2) Fill this image randomly and following the algorithm specified above so that the desired probability of the entire image is realized in the mini-image. 3) Create N of these mini-images and then randomly successively place them in the large image. Unfortunately there are some downfalls to this simplification. 1) given the small size of the mini-images, nailing an exact probability for the entire image is not possible. Example if I want p(2x1)=P(1x2)=0.4, the mini image may only give 0.41 as the closes probability. 2) The mini-images create a pseudo boundary where no overlaps occur which isn't really descriptive of the model this is being used for. 3) There is only a fixed number of mini-images so i'm not sure how random this really is. I'm really just looking to brainstorm about possible solutions to this. My main concern is really to nail down closer probabilities, now one might suggest I just increase the mini-image size. Well I have, and it turns out that in certain cases(p(1x2)=p(2x1)=0.5) the mini-image 16x16 isn't even iteratively solvable.. So it's pretty obvious how difficult it is to randomly solve this for anything greater than 8x8 sizes.. So I'd love to hear some ideas. Thanks

  Read the article

• Logic - Time measurement

  - by user73384

  To measure the following for tasks- Last execution time and maximum execution time for each task. CPU load/time consumed by each task over a defined period informed by application at run time. Maximum CPU load consumed by each task. Tasks have following characteristics- First task runs as background – Event information for entering only Second task - periodic – Event information for entering and exiting from task Third task is interrupt , can start any time – no information available from this task Forth task highest priority interrupt , can start any time – Event information for entering and exiting from task Should use least possible execution time and memory. 32bit increment timer available for time counting. Lets prepare and discuss the logic, It’s OK to have limitations …! Questions on understanding problem statement are welcome

  Read the article

• Given an integer, determine if it is a Palindrome in less than O(n) [on hold]

  - by user134235

  There is an O(n) solution to the problem of determining if an integer is a palindrome below. Is it possible to solve this problem in O(log n) or better? static void IsPalindrome(int Number) { int OrignalNum = Number; int Reverse = 0; int Remainder = 0; if (Number > 0) { while (Number > 0) { Remainder = Number % 10; Reverse = Reverse * 10 + Remainder; Number = Number / 10; } if (OrignalNum == Reverse) Console.WriteLine("It is a Palindrome"); else Console.WriteLine("It is not a Palindrome"); } else Console.WriteLine("Enter Number Again"); }

  Read the article

• How to quickly search through a very large list of strings / records on a database

  - by Giorgio

  I have the following problem: I have a database containing more than 2 million records. Each record has a string field X and I want to display a list of records for which field X contains a certain string. Each record is about 500 bytes in size. To make it more concrete: in the GUI of my application I have a text field where I can enter a string. Above the text field I have a table displaying the (first N, e.g. 100) records that match the string in the text field. When I type or delete one character in the text field, the table content must be updated on the fly. I wonder if there is an efficient way of doing this using appropriate index structures and / or caching. As explained above, I only want to display the first N items that match the query. Therefore, for N small enough, it should not be a big issue loading the matching items from the database. Besides, caching items in main memory can make retrieval faster. I think the main problem is how to find the matching items quickly, given the pattern string. Can I rely on some DBMS facilities, or do I have to build some in-memory index myself? Any ideas? EDIT I have run a first experiment. I have split the records into different text files (at most 200 records per file) and put the files in different directories (I used the content of one data field to determine the directory tree). I end up with about 50000 files in about 40000 directories. I have then run Lucene to index the files. Searching for a string with the Lucene demo program is pretty fast. Splitting and indexing took a few minutes: this is totally acceptable for me because it is a static data set that I want to query. The next step is to integrate Lucene in the main program and use the hits returned by Lucene to load the relevant records into main memory.

  Read the article

• What's a good algorithm for a random, uneven distribution of a fixed amount of a resource?

  - by NickC

  Problem I have X, a positive integer, of some resource, R. There are N potential targets. I want to distribute all of R to the N targets in some "interesting" way. "Interesting" means: Some targets may not get any R. It should rarely be near even (with a majority of target getting near X/N of the resource). There should be at least a small chance of one target getting all of R. Bad solutions The naive approach would be to pick a random target and give one R to it and repeat X times. This would result in too even of an approach. The next idea is to pick a random number between 1 and X and give it to a random target. This results in too large of a number (at least X/2 on average) being given to one target. Question This algorithm will be used frequently and I want the distribution to be interesting and uneven so that the surprise doesn't wear off for users. Is there a good algorithm for something in between these two approaches, that fits the definition of interesting above?

  Read the article

• A look at an example of anti-spam algorithm

  - by pragmaticCamel

  What is a good approach to an anti-spam algorithm for a website similar to reddit? Their anti-spam algorithm seems awfully broken (banning on words in the title and doing a horrible job for that matter). Considering a post spam because it has the word 'spam' in the title is really not a wise choice. Anyway, how can one approach such problem ? Are there any tools that help in such cases? Also, what are the /technical/ reasons behind reddit's choice not using reCAPTCHA on every post submission? It seems like a much better solution than what they have right now. Since reddit is basically a community-driven website why not give such power to the communities' trusted members?

  Read the article

• High-level strategy for distinguishing a regular string from invalid JSON (ie. JSON-like string detection)

  - by Jonline

  Disclaimer On Absence of Code: I have no code to post because I haven't started writing; was looking for more theoretical guidance as I doubt I'll have trouble coding it but am pretty befuddled on what approach(es) would yield best results. I'm not seeking any code, either, though; just direction. Dilemma I'm toying with adding a "magic method"-style feature to a UI I'm building for a client, and it would require intelligently detecting whether or not a string was meant to be JSON as against a simple string. I had considered these general ideas: Look for a sort of arbitrarily-determined acceptable ratio of the frequency of JSON-like syntax (ie. regex to find strings separated by colons; look for colons between curly-braces, etc.) to the number of quote-encapsulated strings + nulls, bools and ints/floats. But the smaller the data set, the more fickle this would get look for key identifiers like opening and closing curly braces... not sure if there even are more easy identifiers, and this doesn't appeal anyway because it's so prescriptive about the kinds of mistakes it could find try incrementally parsing chunks, as those between curly braces, and seeing what proportion of these fractional statements turn out to be valid JSON; this seems like it would suffer less than (1) from smaller datasets, but would probably be much more processing-intensive, and very susceptible to a missing or inverted brace Just curious if the computational folks or algorithm pros out there had any approaches in mind that my semantics-oriented brain might have missed. PS: It occurs to me that natural language processing, about which I am totally ignorant, might be a cool approach; but, if NLP is a good strategy here, it sort of doesn't matter because I have zero experience with it and don't have time to learn & then implement/ this feature isn't worth it to the client.

  Read the article

• Matching users based on a series of questions

  - by SeanWM

  I'm trying to figure out a way to match users based on specific personality traits. Each trait will have its own category. I figure in my user table I'll add a column for each category: id name cat1 cat2 cat3 1 Sean ? ? ? 2 Other ? ? ? Let's say I ask each user 3 questions in each category. For each question, you can answer one of the following: No, Maybe, Yes How would I calculate one number based off the answers in those 3 questions that would hold a value I can compare other users to? I was thinking having some sort of weight. Like: No -> 0 Maybe -> 1 Yes -> 2 Then doing some sort of meaningful calculation. I want to end up with something like this so I can query the users and find who matches close: id name cat1 cat2 cat3 1 Sean 4 5 1 2 Other 1 2 5 In the situation above, the users don't really match. I'd want to match with someone with a +1 or -1 of my score in each category. I'm not a math guy so I'm just looking for some ideas to get me started.

  Read the article

• Algorithm to generate N random numbers between A and B which sum up to X

  - by Shaamaan

  This problem seemed like something which should be solvable with but a few lines of code. Unfortunately, once I actually started to write the thing, I've realized it's not as simple as it sounds. What I need is a set of X random numbers, each of which is between A and B and they all add up to X. The exact variables for the problem I'm facing seem to be even simpler: I need 5 numbers, between -1 and 1 (note: these are decimal numbers), which add up to 1. My initial "few lines of code, should be easy" approach was to randomize 4 numbers between -1 and 1 (which is simple enough), and then make the last one 1-(sum of previous numbers). This quickly proved wrong, as the last number could just as well be larger than 1 or smaller than -1. What would be the best way to approach this problem? PS. Just for reference: I'm using C#, but I don't think it matters. I'm actually having trouble creating a good enough solution for the problem in my head.

  Read the article

• Efficient way to find unique elements in a vector compared against multiple vectors

  - by SyncMaster

  I am trying find the number of unique elements in a vector compared against multiple vectors using C++. Suppose I have, v1: 5, 8, 13, 16, 20 v2: 2, 4, 6, 8 v3: 20 v4: 1, 2, 3, 4, 5, 6, 7 v5: 1, 3, 5, 7, 11, 13, 15 The number of unique elements in v1 is 1 (i.e. number 16). I tried two approaches. Added vectors v2,v3,v4 and v5 into a vector of vector. For each element in v1, checked if the element is present in any of the other vectors. Combined all the vectors v2,v3,v4 and v5 using merge sort into a single vector and compared it against v1 to find the unique elements. Note: sample_vector = v1 and all_vectors_merged contains v2,v3,v4,v5 //Method 1 unsigned int compute_unique_elements_1(vector<unsigned int> sample_vector,vector<vector<unsigned int> > all_vectors_merged) { unsigned int duplicate = 0; for (unsigned int i = 0; i < sample_vector.size(); i++) { for (unsigned int j = 0; j < all_vectors_merged.size(); j++) { if (std::find(all_vectors_merged.at(j).begin(), all_vectors_merged.at(j).end(), sample_vector.at(i)) != all_vectors_merged.at(j).end()) { duplicate++; } } } return sample_vector.size()-duplicate; } // Method 2 unsigned int compute_unique_elements_2(vector<unsigned int> sample_vector, vector<unsigned int> all_vectors_merged) { unsigned int unique = 0; unsigned int i = 0, j = 0; while (i < sample_vector.size() && j < all_vectors_merged.size()) { if (sample_vector.at(i) > all_vectors_merged.at(j)) { j++; } else if (sample_vector.at(i) < all_vectors_merged.at(j)) { i++; unique ++; } else { i++; j++; } } if (i < sample_vector.size()) { unique += sample_vector.size() - i; } return unique; } Of these two techniques, I see that Method 2 gives faster results. 1) Method 1: Is there a more efficient way to find the elements than running std::find on all the vectors for all the elements in v1. 2) Method 2: Extra overhead in comparing vectors v2,v3,v4,v5 and sorting them. How can I do this in a better way?

  Read the article

• Minimizing use of paper

  - by Abody97

  I've recently faced this problem in a dynamic programming curriculum, and I honestly have no idea about how to determine the appropriate state. You're given N (1 <= N <= 70) paragraphs and M (1 <= M <= N) figures. Each paragraph i requires PL_i (1 <= PL_i <= 100) lines and references at most one figure. Each figure is referenced exactly once (i.e., no two paragraphs can reference the same figure, and for each figure there's a paragraph that references it.) Each figure requires PF_i (1 <= PF_i <= 100) lines. The task is to distribute those figures and paragraphs on paper in the order they're given, where one paper fits for L lines at most. No paragraph or figure is too large to fit on one paper. If a paragraph x placed on paper x_p references a figure y then y must be placed on either the paper x_p - 1 or x_p or x_p + 1. We have to find the minimum number of lines (and thus pages) to allocate in order to distribute all the figures and paragraphs. Any help would be extremely appreciated. Thanks in advance!

  Read the article

• What is an efficient algorithm for randomly assigning a pool of objects to a parent using specific rules

  - by maple_shaft

  I need some expert answers to help me determine the most efficient algorithm in this scenario. Consider the following data structures: type B { A parent; } type A { set<B> children; integer minimumChildrenAllowed; integer maximumChildrenAllowed; } I have a situation where I need to fetch all the orphan children (there could be hundreds of thousands of these) and assign them RANDOMLY to A type parents based on the following rules. At the end of the job, there should be no orphans left At the end of the job, no object A should have less children than its predesignated minimum. At the end of the job, no object A should have more children than its predesignated maximum. If we run out of A objects then we should create a new A with default values for minimum and maximum and assign remaining orphans to these objects. The distribution of children should be as evenly distributed as possible. There may already be some children assigned to A before the job starts. I was toying with how to do this but I am afraid that I would just end up looping across the parents sorted from smallest to largest, and then grab an orphan for each parent. I was wondering if there is a more efficient way to handle this?

  Read the article

• What is a good algorithm to distribute items with specific requirements?

  - by user66160

  I have to programmatically distribute a set of items to some entities, but there are rules both on the items and on the entities like so: Item one: 100 units, only entities from Foo Item two: 200 units, no restrictions Item three: 100 units, only entities that have Bar Entity one: Only items that have Baz Entity one hundred: No items that have Fubar I only need to be pointed in the right direction, I'll research and learn the suggested methods.

  Read the article

• How to create distinct set from other sets?

  - by shyam_baidya

  While solving the problems on Techgig.com, I got struck with one one of the problem. The problem is like this: A company organizes two trips for their employees in a year. They want to know whether all the employees can be sent on the trip or not. The condition is like, no employee can go on both the trips. Also to determine which employee can go together the constraint is that the employees who have worked together in past won't be in the same group. Examples of the problems: Suppose the work history is given as follows: {(1,2),(2,3),(3,4)}; then it is possible to accommodate all the four employees in two trips (one trip consisting of employees 1& 3 and other having employees 2 & 4). Neither of the two employees in the same trip have worked together in past. Suppose the work history is given as {(1,2),(1,3),(2,3)} then there is no way possible to have two trips satisfying the company rule and accommodating all the employees. Can anyone tell me how to proceed on this problem?

  Read the article

• Scale an image with unscalable parts

  - by Uko

  Brief description of problem: imagine having some vector picture(s) and text annotations on the sides outside of the picture(s). Now the task is to scale the whole composition while preserving the aspect ratio in order to fit some view-port. The tricky part is that the text is not scalable only the picture(s). The distance between text and the image is still relative to the whole image, but the text size is always a constant. Example: let's assume that our total composition is two times larger than a view-port. Then we can just scale it by 1/2. But because the text parts are a fixed font size, they will become larger than we expect and won't fit in the view-port. One option I can think of is an iterative process where we repeatedly scale our composition until the delta between it and the view-port satisfies some precision. But this algorithm is quite costly as it involves working with the graphics and the image may be composed of a lot of components which will lead to a lot of matrix computations. What's more, this solution seems to be hard to debug, extend, etc. Are there any other approaches to solving this scaling problem?

  Read the article

• Fastest way to check if two square 2D arrays are rotationally and reflectively distinct

  - by kustrle

  The best idea I have so far is to rotate first array by {0, 90, 180, 270} degrees and reflect it horizontally or/and vertically. We basically get 16 variations [1] of first array and compare them with second array. if none of them matches the two arrays are rotationally and reflectively distinct. I am wondering if there is more optimal solution than this brute-force approach? [1] 0deg, no reflection 0deg, reflect over x 0deg, reflect over y 0deg, reflect over x and y 90deg, no reflection ...

  Read the article

• Good choice of languages for making a program that manages and organizes business? [closed]

  - by Ronney P

  I've been reading questions and discussions on this website but haven't made an account to start talking or asking anything I had doubts in so please bare with a newbie here. What are specific languages that have are able to make a program that will record, and organize things such as hours, salaries, payments? Also solve business problems, mostly with payments, how much money there will be after interest, taxes and such. Anyway, I've been looking into COBOL, C++, Java, HTML, JavaScript, VB.NET and a couple more. Which ones should I focus on and look into more? I very much appreciate any answers. Thank you.

  Read the article

• Need to organize words based on their components, any other way aside from brute force?

  - by Lathan

  I'm not sure if this process has a name. I have some words (about 9,000). They are in Japanese, but I'll try to explain this using English words. I want to categorize the words by the components (in English, letters). A B C act bar play This should create: A: play B: bar C: act Now, 'a' appears in all 3 words, but I want to make sure that each category (letter) has at least word. Now, it would make sense to delete a word after it's used, but there are a few cases where 2 letters make up one word and that's each letter's only word--so I'd like to account for that somehow. Is there an approach for solving this aside from brute force? Dynamic programming perhaps? Even a name for this process (if it exists) would be great.

  Read the article

• What can I learn to build a (kind of) recommendation system?

  - by lsmagalhaes

  I'm learning how to develop an android app (nothing serious, just for learning and fun), so I devised the following goal: an app that learns with users actions and, some time later, starts to suggest some useful things. For example: The user add some notes daily, in the morning, and mark some of them as done generally on thursdays and sundays, at evening. Based on that behaviour and the relation of the notes marked as done, the app will prioritize notes that are more propense to be marked, and avoid notifying in days where no note is marked. This is a silly example but I think it ilustrates well what I want to do. I know this is a matter of machine learning, but I don't know where I should start learning. To anyone interested, I'm build a backend in Python, so any libraries or frameworks in this language are very welcome. The frontend, by the way, is sencha touch + phonegap.

  Read the article

• What is the Big-Oh nitation for this? [closed]

  - by laniam

  procedure quartersearch (x : inter, a1, a2, ?, an) : increasing integers) i := 1{i is left endpoint of search interval} ? j := n {j is right endpoint of search interval} while i < j begin m :=? ?(i + j)? / 4 if x am then ?i := m+1 else if x am then ?m : = ?(i + j)? / 4 else if x am then m := 2 ?(i + j)? /4 else ?if x am then m := 3 ?(i + j)? /4 else j := m end if x = ai then location := i else location := 0

  Read the article

< Previous Page | 13 14 15 16 17 18 19 20 21 22 23 24  | Next Page >