Search Results

Search found 5655 results on 227 pages for 'stl algorithm'.

facebook twitter digg google delicious technorati stumbleupon myspace wordpress linkedin gmail igoogle windows live tumblr viadeo yahoo buzz yahoo mail yahoo bookmarks favorites email print

Page 56/227 | < Previous Page | 52 53 54 55 56 57 58 59 60 61 62 63  | Next Page >

  • Data structure to build and lookup set of integer ranges

    - by actual
    I have a set of uint32 integers, there may be millions of items in the set. 50-70% of them are consecutive, but in input stream they appear in unpredictable order. I need to: Compress this set into ranges to achieve space efficient representation. Already implemented this using trivial algorithm, since ranges computed only once speed is not important here. After this transformation number of resulting ranges is typically within 5 000-10 000, many of them are single-item, of course. Test membership of some integer, information about specific range in the set is not required. This one must be very fast -- O(1). Was thinking about minimal perfect hash functions, but they do not play well with ranges. Bitsets are very space inefficient. Other structures, like binary trees, has complexity of O(log n), worst thing with them that implementation make many conditional jumps and processor can not predict them well giving poor performance. Is there any data structure or algorithm specialized in integer ranges to solve this task?

    Read the article

  • Sorted queue with dropping out elements

    - by ffriend
    I have a list of jobs and queue of workers waiting for these jobs. All the jobs are the same, but workers are different and sorted by their ability to perform the job. That is, first person can do this job best of all, second does it just a little bit worse and so on. Job is always assigned to the person with the highest skills from those who are free at that moment. When person is assigned a job, he drops out of the queue for some time. But when he is done, he gets back to his position. So, for example, at some moment in time worker queue looks like: [x, x, .83, x, .7, .63, .55, .54, .48, ...] where x's stand for missing workers and numbers show skill level of left workers. When there's a new job, it is assigned to 3rd worker as the one with highest skill of available workers. So next moment queue looks like: [x, x, x, x, .7, .63, .55, .54, .48, ...] Let's say, that at this moment worker #2 finishes his job and gets back to the list: [x, .91, x, x, .7, .63, .55, .54, .48, ...] I hope the process is completely clear now. My question is what algorithm and data structure to use to implement quick search and deletion of worker and insertion back to his position. For the moment the best approach I can see is to use Fibonacci heap that have amortized O(log n) for deleting minimal element (assigning job and deleting worker from queue) and O(1) for inserting him back, which is pretty good. But is there even better algorithm / data structure that possibly take into account the fact that elements are already sorted and only drop of the queue from time to time?

    Read the article

  • Convert a binary tree to linked list, breadth first, constant storage/destructive

    - by Merlyn Morgan-Graham
    This is not homework, and I don't need to answer it, but now I have become obsessed :) The problem is: Design an algorithm to destructively flatten a binary tree to a linked list, breadth-first. Okay, easy enough. Just build a queue, and do what you have to. That was the warm-up. Now, implement it with constant storage (recursion, if you can figure out an answer using it, is logarithmic storage, not constant). I found a solution to this problem on the Internet about a year back, but now I've forgotten it, and I want to know :) The trick, as far as I remember, involved using the tree to implement the queue, taking advantage of the destructive nature of the algorithm. When you are linking the list, you are also pushing an item into the queue. Each time I try to solve this, I lose nodes (such as each time I link the next node/add to the queue), I require extra storage, or I can't figure out the convoluted method I need to get back to a node that has the pointer I need. Even the link to that original article/post would be useful to me :) Google is giving me no joy. Edit: Jérémie pointed out that there is a fairly simple (and well known answer) if you have a parent pointer. While I now think he is correct about the original solution containing a parent pointer, I really wanted to solve the problem without it :) The refined requirements use this definition for the node: struct tree_node { int value; tree_node* left; tree_node* right; };

    Read the article

  • please help me to solve problem

    - by davit-datuashvili
    first of all this is not homework and nobody tag it as homewrok i did not understand this porblem can anybody explain me?this is not english problem it is just misunderstanding what problem say Consider the problem of neatly printing a paragraph on a printer. The input text is a sequence of n words of lengths l1 , l2 , . . . , ln , measured in characters. We want to print this paragraph neatly on a number of lines that hold a maximum of M characters each. Our criterion of “neatness” is as follows. If a given line contains words i through j , where i = j , and we leave exactly one space between words, the number of extra space characters at the end of the line is M - j + i -(k=i,k< j,k++) lk , which must be nonnegative so that the words fit on the line. We wish to minimize the sum, over all lines except the last, of the cubes of the numbers of extra space characters at the ends of lines. Give a dynamic-programming algorithm to print a paragraph of n words neatly on a printer. Analyze the running time and space requirements of your algorithm.

    Read the article

  • Solving algorithm for a simple problem

    - by maolo
    I'm searching for an algorithm (should be rather simple for you guys) that does nothing but solve the chicken or the egg problem. I need to implement this in C++. What I've got so far is: enum ChickenOrEgg { Chicken, Egg }; ChickenOrEgg WhatWasFirst( ) { ChickenOrEgg ret; // magic happens here return ret; } // testing #include <iostream> using namespace std; if ( WhatWasFirst( ) == Chicken ) { cout << "The chicken was first."; } else { cout << "The egg was first."; } cout << endl; Question: How could the pseudocode for the solving function look? Notes: This is not a joke, not even a bad one. Before you close this, think of why this isn't a perfectly valid question according to the SO rules. If someone here can actually implement an algorithm solving the problem he gets $500 in cookies from me (that's a hell lot of cookies!). Please don't tell me that this is my homework, what teacher would ever give his students homework like that?

    Read the article

  • Combine Arbitrary number of polygons together

    - by Jakobud
    I have an arbitrary number of polygons (hexes in this case) that are arranged randomly, but they are all touching another hex. Each individual hex has 6 x,y vertices. The vertex's are known for all the hexes. Can anyone point me in the direction of an algorithm that will combine all the hexes into a single polygon? Essentially I'm just looking for a function that spits out an array of vertex locations that are ordered in a way that when drawing lines from one to the next, it forms the polygon. This is my method so far: Create array of all the vertices for all the hexes. Determine the number of times a vertex occurs in the array If vertex is in the array 3+ times, delete the vertices from the array. If vertex is in the array 2 times, delete one of them. The next step is tricky though. I'm using canvas to draw out these polygons, which essentially involves drawing a line from one vertex to the next. So the order of the vertices in the final array is important. It can't be sorted arbitrarily. Also, I'm not looking for a "convex hull" algorithm, as that would not draw the polygon correctly. Are there any functions out there that do something like this? Am I on the right track or is there a better more efficient way?

    Read the article

  • What is the n in O(n) when comparing sorting algorithms?

    - by Mumfi
    The question is rather simple, but I just can't find a good enough answer. I've taken a look at the most upvoted question regarding the Big-Oh notation, namely this: Plain English explanation of Big O It says there that: For example, sorting algorithms are typically compared based on comparison operations (comparing two nodes to determine their relative ordering). Now let's consider the simple bubble sort algorithm: for (int i = arr.length - 1; i > 0 ; i--) { for (int j = 0; j<i; j++) { if (arr[j] > arr[j+1]) { switchPlaces(...) } } } I know that worst case is O(n^2) and best case is O(n), but what is n exactly? If we attempt to sort an already sorted algorithm (best case), we would end up doing nothing, so why is it still O(n)? We are looping through 2 for-loops still, so if anything it should be O(n^2). n can't be the number of comparison operations, because we still compare all the elements, right? This confuses me, and I appreciate if someone could help me.

    Read the article

  • Making more recent items more likely to be drawn

    - by bobo
    There are a few hundred of book records in the database and each record has a publish time. In the homepage of the website, I am required to write some codes to randomly pick 10 books and put them there. The requirement is that newer books need to have higher chances of getting displayed. Since the time is an integer, I am thinking like this to calculate the probability for each book: Probability of a book to be drawn = (current time - publish time of the book) / ((current time - publish time of the book1) + (current time - publish time of the book1) + ... (current time - publish time of the bookn)) After a book is drawn, the next round of the loop will minus the (current time - publish time of the book) from the denominator and recalculate the probability for each of the remaining books, the loop continues until 10 books have been drawn. Is this algorithm a correct one? By the way, the website is written in PHP. Feel free to suggest some PHP codes if you have a better algorithm in your mind. Many thanks to you all.

    Read the article

  • Different behavior of functors (copies, assignments) in VS2010 (compared with VS2005)

    - by Patrick
    When moving from VS2005 to VS2010 we noticed a performance decrease, which seemed to be caused by additional copies of a functor. The following code illustrates the problem. It is essential to have a map where the value itself is a set. On both the map and the set we defined a comparison functor (which is templated in the example). #include <iostream> #include <map> #include <set> class A { public: A(int i, char c) : m_i(i), m_c(c) { std::cout << "Construct object " << m_c << m_i << std::endl; } A(const A &a) : m_i(a.m_i), m_c(a.m_c) { std::cout << "Copy object " << m_c << m_i << std::endl; } ~A() { std::cout << "Destruct object " << m_c << m_i << std::endl; } void operator= (const A &a) { m_i = a.m_i; m_c = a.m_c; std::cout << "Assign object " << m_c << m_i << std::endl; } int m_i; char m_c; }; class B : public A { public: B(int i) : A(i, 'B') { } static const char s_c = 'B'; }; class C : public A { public: C(int i) : A(i, 'C') { } static const char s_c = 'C'; }; template <class X> class compareA { public: compareA() : m_i(999) { std::cout << "Construct functor " << X::s_c << m_i << std::endl; } compareA(const compareA &a) : m_i(a.m_i) { std::cout << "Copy functor " << X::s_c << m_i << std::endl; } ~compareA() { std::cout << "Destruct functor " << X::s_c << m_i << std::endl; } void operator= (const compareA &a) { m_i = a.m_i; std::cout << "Assign functor " << X::s_c << m_i << std::endl; } bool operator() (const X &x1, const X &x2) const { std::cout << "Comparing object " << x1.m_i << " with " << x2.m_i << std::endl; return x1.m_i < x2.m_i; } private: int m_i; }; typedef std::set<C, compareA<C> > SetTest; typedef std::map<B, SetTest, compareA<B> > MapTest; int main() { int i = 0; std::cout << "--- " << i++ << std::endl; MapTest mapTest; std::cout << "--- " << i++ << std::endl; SetTest &setTest = mapTest[0]; std::cout << "--- " << i++ << std::endl; } If I compile this code with VS2005 I get the following output: --- 0 Construct functor B999 Copy functor B999 Copy functor B999 Destruct functor B999 Destruct functor B999 --- 1 Construct object B0 Construct functor C999 Copy functor C999 Copy functor C999 Destruct functor C999 Destruct functor C999 Copy object B0 Copy functor C999 Copy functor C999 Copy functor C999 Destruct functor C999 Destruct functor C999 Copy object B0 Copy functor C999 Copy functor C999 Copy functor C999 Destruct functor C999 Destruct functor C999 Destruct functor C999 Destruct object B0 Destruct functor C999 Destruct object B0 --- 2 If I compile this with VS2010, I get the following output: --- 0 Construct functor B999 Copy functor B999 Copy functor B999 Destruct functor B999 Destruct functor B999 --- 1 Construct object B0 Construct functor C999 Copy functor C999 Copy functor C999 Destruct functor C999 Destruct functor C999 Copy object B0 Copy functor C999 Copy functor C999 Copy functor C999 Destruct functor C999 Destruct functor C999 Copy functor C999 Assign functor C999 Assign functor C999 Destruct functor C999 Copy object B0 Copy functor C999 Copy functor C999 Copy functor C999 Destruct functor C999 Destruct functor C999 Copy functor C999 Assign functor C999 Assign functor C999 Destruct functor C999 Destruct functor C999 Destruct object B0 Destruct functor C999 Destruct object B0 --- 2 The output for the first statement (constructing the map) is identical. The output for the second statement (creating the first element in the map and getting a reference to it), is much bigger in the VS2010 case: Copy constructor of functor: 10 times vs 8 times Assignment of functor: 2 times vs. 0 times Destructor of functor: 10 times vs 8 times My questions are: Why does the STL copy a functor? Isn't it enough to construct it once for every instantiation of the set? Why is the functor constructed more in the VS2010 case than in the VS2005 case? (didn't check VS2008) And why is it assigned two times in VS2010 and not in VS2005? Are there any tricks to avoid the copy of functors? I saw a similar question at http://stackoverflow.com/questions/2216041/prevent-unnecessary-copies-of-c-functor-objects but I'm not sure that's the same question. Thanks in advance, Patrick

    Read the article

  • Using a map with set_intersection

    - by Robin Welch
    Not used set_intersection before, but I believe it will work with maps. I wrote the following example code but it doesn't give me what I'd expect: #include <map> #include <string> #include <iostream> #include <algorithm> using namespace std; struct Money { double amount; string currency; bool operator< ( const Money& rhs ) const { if ( amount != rhs.amount ) return ( amount < rhs.amount ); return ( currency < rhs.currency ); } }; int main( int argc, char* argv[] ) { Money mn[] = { { 2.32, "USD" }, { 2.76, "USD" }, { 4.30, "GBP" }, { 1.21, "GBP" }, { 1.37, "GBP" }, { 6.74, "GBP" }, { 2.55, "EUR" } }; typedef pair< int, Money > MoneyPair; typedef map< int, Money > MoneyMap; MoneyMap map1; map1.insert( MoneyPair( 1, mn[1] ) ); map1.insert( MoneyPair( 2, mn[2] ) ); map1.insert( MoneyPair( 3, mn[3] ) ); // (3) map1.insert( MoneyPair( 4, mn[4] ) ); // (4) MoneyMap map2; map1.insert( MoneyPair( 3, mn[3] ) ); // (3) map1.insert( MoneyPair( 4, mn[4] ) ); // (4) map1.insert( MoneyPair( 5, mn[5] ) ); map1.insert( MoneyPair( 6, mn[6] ) ); map1.insert( MoneyPair( 7, mn[7] ) ); MoneyMap out; MoneyMap::iterator out_itr( out.begin() ); set_intersection( map1.begin(), map1.end(), map2.begin(), map2.end(), inserter( out, out_itr ) ); cout << "intersection has " << out.size() << " elements." << endl; return 0; } Since the pair labelled (3) and (4) appear in both maps, I was expecting that I'd get 2 elements in the intersection, but no, I get: intersection has 0 elements. I'm sure this is something to do with the comparitor on the map / pair but can't figure it out.

    Read the article

  • How are PID's generated?

    - by Helltone
    On *nix, PIDs are unique identifiers for running processes. How are PID's generated? Is it just an integer which gets incremented or a more complex structure such as a list? How do they get recycled? By recycling I mean that, when a process terminates, it's PID will eventually be reused by another process.

    Read the article

  • A star vs internet routing pathfinding

    - by alan2here
    In many respects pathfinding algorythms like A star for finding the shortest route though graphs are similar to the pathfinding on the internet when routing trafic. However the pathfinding routers perform seem to have remarkable properties. As I understand it: It's very perfromant. New nodes can be added at any time that use a free address from a finite (not tree like) address space. It's real routing, like A*, theres never any doubling back for example. IP addresses don't have to be geographicly nearby. The network reacts quickly to changes to the networks shape, for example if a line is down. Routers share information and it takes time for new IP's to be registered everywhere, but presumably every router dosn't have to store a list of all the addresses each of it's directions leads most directly to. I can't find this information elsewhere however I don't know where to look or what search tearms to use. I'm looking for a basic, general, high level description to the algorithms workings, from the point of view of an individual router.

    Read the article

  • Utility to optimally distribute files onto multiple DVDs?

    - by Alex R
    I have a bunch of media files which I want to record to DVD, but since each DVD only fits 4.5GB, I have to find the optimal way to organize the files to use the minimum number of DVDs (otherwise the empty space left in each DVD can easily add up). Are there any tools to help with this? Many years ago there was a DOS utility to do this with floppy disks.

    Read the article

  • How to make negate_unary work with any type?

    - by Chan
    Hi, Following this question: How to negate a predicate function using operator ! in C++? I want to create an operator ! can work with any functor that inherited from unary_function. I tried: template<typename T> inline std::unary_negate<T> operator !( const T& pred ) { return std::not1( pred ); } The compiler complained: Error 5 error C2955: 'std::unary_function' : use of class template requires template argument list c:\program files\microsoft visual studio 10.0\vc\include\xfunctional 223 1 Graphic Error 7 error C2451: conditional expression of type 'std::unary_negate<_Fn1>' is illegal c:\program files\microsoft visual studio 10.0\vc\include\ostream 529 1 Graphic Error 3 error C2146: syntax error : missing ',' before identifier 'argument_type' c:\program files\microsoft visual studio 10.0\vc\include\xfunctional 222 1 Graphic Error 4 error C2065: 'argument_type' : undeclared identifier c:\program files\microsoft visual studio 10.0\vc\include\xfunctional 222 1 Graphic Error 2 error C2039: 'argument_type' : is not a member of 'std::basic_ostream<_Elem,_Traits>::sentry' c:\program files\microsoft visual studio 10.0\vc\include\xfunctional 222 1 Graphic Error 6 error C2039: 'argument_type' : is not a member of 'std::basic_ostream<_Elem,_Traits>::sentry' c:\program files\microsoft visual studio 10.0\vc\include\xfunctional 230 1 Graphic Any idea? Update Follow "templatetypedef" solution, I got new error: Error 3 error C2831: 'operator !' cannot have default parameters c:\visual studio 2010 projects\graphic\graphic\main.cpp 39 1 Graphic Error 2 error C2808: unary 'operator !' has too many formal parameters c:\visual studio 2010 projects\graphic\graphic\main.cpp 39 1 Graphic Error 4 error C2675: unary '!' : 'is_prime' does not define this operator or a conversion to a type acceptable to the predefined operator c:\visual studio 2010 projects\graphic\graphic\main.cpp 52 1 Graphic Update 1 Complete code: #include <iostream> #include <functional> #include <utility> #include <cmath> #include <algorithm> #include <iterator> #include <string> #include <boost/assign.hpp> #include <boost/assign/std/vector.hpp> #include <boost/assign/std/map.hpp> #include <boost/assign/std/set.hpp> #include <boost/assign/std/list.hpp> #include <boost/assign/std/stack.hpp> #include <boost/assign/std/deque.hpp> struct is_prime : std::unary_function<int, bool> { bool operator()( int n ) const { if( n < 2 ) return 0; if( n == 2 || n == 3 ) return 1; if( n % 2 == 0 || n % 3 == 0 ) return 0; int upper_bound = std::sqrt( static_cast<double>( n ) ); for( int pf = 5, step = 2; pf <= upper_bound; ) { if( n % pf == 0 ) return 0; pf += step; step = 6 - step; } return 1; } }; /* template<typename T> inline std::unary_negate<T> operator !( const T& pred, typename T::argument_type* dummy = 0 ) { return std::not1<T>( pred ); } */ inline std::unary_negate<is_prime> operator !( const is_prime& pred ) { return std::not1( pred ); } template<typename T> inline void print_con( const T& con, const std::string& ms = "", const std::string& sep = ", " ) { std::cout << ms << '\n'; std::copy( con.begin(), con.end(), std::ostream_iterator<typename T::value_type>( std::cout, sep.c_str() ) ); std::cout << "\n\n"; } int main() { using namespace boost::assign; std::vector<int> nums; nums += 1, 3, 5, 7, 9; nums.erase( remove_if( nums.begin(), nums.end(), !is_prime() ), nums.end() ); print_con( nums, "After remove all primes" ); } Thanks, Chan Nguyen

    Read the article

  • How/where to run the algorithm on large dataset?

    - by niko
    I would like to run the PageRank algorithm on graph with 4 000 000 nodes and around 45 000 000 edges. Currently I use neo4j graph databse and classic relational database (postgres) and for software projects I mostly use C# and Java. Does anyone know what would be the best way to perform a PageRank computation on such graph? Is there any way to modify the PageRank algorithm in order to run it at home computer or server (48GB RAM) or is there any useful cloud service to push the data along the algorithm and retrieve the results? At this stage the project is at the research stage so in case of using cloud service if possible, would like to use such provider that doesn't require much administration and service setup, but instead focus just on running the algorith once and get the results without much overhead administration work.

    Read the article

  • Solved: Chrome v18, self signed certs and &ldquo;signed using a weak signature algorithm&rdquo;

    - by David Christiansen
    So chrome has just updated itself automatically and you are now running v18 – great. Or is it… If like me, you are someone that are running sites using a self-signed SSL Certificate (i.e. when running a site on a developer machine) you may come across the following lovely message; Fear not, this is likely as a result of you following instructions you found on the apache openssl site which results in a self signed cert using the MD5 signature hashing algorithm. Using OpenSSL The simple fix is to generate a new certificate specifying to use the SHA512 signature hashing algorithm, like so; openssl req -new -x509 -sha512 -nodes -out server.crt -keyout server.key Simples! Now, you should be able to confirm the signature algorithm used is sha512 by looking at the details tab of certificate Notes If you change your certificate, be sure to reapply any private key permissions you require – such as allowing access to the application pool user.

    Read the article

  • Who owns the code, who owns the algorithm, who owns the idea?

    - by Vorac
    This question got me thinking what products of the programming effort belong to the employer, and what don't. The two extremes are (0) the code - it apparently belongs to the employer and (1) the learned personal and technical skills. But what is in between? Who owns the pseudocode/algorithm? Who owns the general idea of the algorithm? Who owns the know-how that such an algorithm may serve some useful purpose (e.g. on this site questions are values, as well as answers)? Also: Who owns an idea on the web?

    Read the article

  • What is the difference between these two nloglog(n) sorting algorithms? (Andersson et al., 1995 vs.

    - by Yktula
    Swanepoel's comment here lead me to this paper. Then, searching for an implementation in C, I came across this, which referenced another paper on an algorithm described here. Both papers describe integer sorting algorithms that run in O(nloglog(n)) time. What is the difference between the two? Have there been any more recent findings about this topic? Andersson et al., 1995 Han, 2004

    Read the article

  • Dijkstra’s algorithms - a complete list

    - by baris_a
    Hi guys, I have recently asked a question about one of the Dijkstra’s algorithms. But, almost everyone thought it was shortest path. Therefore, I opened this post to gather all the algorithms that were invented by Dijkstra. Please add any if you know. Thanks in advance. 1 ) Shunting-yard algorithm

    Read the article

  • LRU cache design

    - by user297850
    Least Recently Used (LRU) Cache is to discard the least recently used items first How do you design and implement such a cache class? The design requirements are as follows: 1) find the item as fast as we can 2) Once a cache misses and a cache is full, we need to replace the least recently used item as fast as possible. How to analyze and implement this question in terms of design pattern and algorithm design?

    Read the article

  • 2D packing with obstacles

    - by cime
    Anybody know of an efficient algorithm for moving rectangles in a square which contains obstacles? Rectangles: can rotate can move must not collide with obstacles (black squares) Obstacles: can't be moved can be added anywhere Goal: move rectangles until you can

    Read the article

facebook twitter digg google delicious technorati stumbleupon myspace wordpress linkedin gmail igoogle windows live tumblr viadeo yahoo buzz yahoo mail yahoo bookmarks favorites email print

< Previous Page | 52 53 54 55 56 57 58 59 60 61 62 63  | Next Page >