Search Results

Search found 73 results on 3 pages for 'quicksort'.

Page 3/3 | < Previous Page | 1 2 3 

• Random Page Cost and Planning

  - by Dave Jarvis

  A query (see below) that extracts climate data from weather stations within a given radius of a city using the dates for which those weather stations actually have data. The query uses the table's only index, rather effectively: CREATE UNIQUE INDEX measurement_001_stc_idx ON climate.measurement_001 USING btree (station_id, taken, category_id); Reducing the server's configuration value for random_page_cost from 2.0 to 1.1 had a massive performance improvement for the given range (nearly an order of magnitude) because it suggested to PostgreSQL that it should use the index. While the results now return in 5 seconds (down from ~85 seconds), problematic lines remain. Bumping the query's end date by a single year causes a full table scan: sc.taken_start >= '1900-01-01'::date AND sc.taken_end <= '1997-12-31'::date AND How do I persuade PostgreSQL to use the indexes regardless of years between the two dates? (A full table scan against 43 million rows is probably not the best plan.) Find the EXPLAIN ANALYSE results below the query. Thank you! Query SELECT extract(YEAR FROM m.taken) AS year, avg(m.amount) AS amount FROM climate.city c, climate.station s, climate.station_category sc, climate.measurement m WHERE c.id = 5182 AND earth_distance( ll_to_earth(c.latitude_decimal,c.longitude_decimal), ll_to_earth(s.latitude_decimal,s.longitude_decimal)) / 1000 <= 30 AND s.elevation BETWEEN 0 AND 3000 AND s.applicable = TRUE AND sc.station_id = s.id AND sc.category_id = 1 AND sc.taken_start >= '1900-01-01'::date AND sc.taken_end <= '1996-12-31'::date AND m.station_id = s.id AND m.taken BETWEEN sc.taken_start AND sc.taken_end AND m.category_id = sc.category_id GROUP BY extract(YEAR FROM m.taken) ORDER BY extract(YEAR FROM m.taken) 1900 to 1996: Index "Sort (cost=1348597.71..1348598.21 rows=200 width=12) (actual time=2268.929..2268.935 rows=92 loops=1)" " Sort Key: (date_part('year'::text, (m.taken)::timestamp without time zone))" " Sort Method: quicksort Memory: 32kB" " -> HashAggregate (cost=1348586.56..1348590.06 rows=200 width=12) (actual time=2268.829..2268.886 rows=92 loops=1)" " -> Nested Loop (cost=0.00..1344864.01 rows=744510 width=12) (actual time=0.807..2084.206 rows=134893 loops=1)" " Join Filter: ((m.taken >= sc.taken_start) AND (m.taken <= sc.taken_end) AND (sc.station_id = m.station_id))" " -> Nested Loop (cost=0.00..12755.07 rows=1220 width=18) (actual time=0.502..521.937 rows=23 loops=1)" " Join Filter: ((sec_to_gc(cube_distance((ll_to_earth((c.latitude_decimal)::double precision, (c.longitude_decimal)::double precision))::cube, (ll_to_earth((s.latitude_decimal)::double precision, (s.longitude_decimal)::double precision))::cube)) / 1000::double precision) <= 30::double precision)" " -> Index Scan using city_pkey1 on city c (cost=0.00..2.47 rows=1 width=16) (actual time=0.014..0.015 rows=1 loops=1)" " Index Cond: (id = 5182)" " -> Nested Loop (cost=0.00..9907.73 rows=3659 width=34) (actual time=0.014..28.937 rows=3458 loops=1)" " -> Seq Scan on station_category sc (cost=0.00..970.20 rows=3659 width=14) (actual time=0.008..10.947 rows=3458 loops=1)" " Filter: ((taken_start >= '1900-01-01'::date) AND (taken_end <= '1996-12-31'::date) AND (category_id = 1))" " -> Index Scan using station_pkey1 on station s (cost=0.00..2.43 rows=1 width=20) (actual time=0.004..0.004 rows=1 loops=3458)" " Index Cond: (s.id = sc.station_id)" " Filter: (s.applicable AND (s.elevation >= 0) AND (s.elevation <= 3000))" " -> Append (cost=0.00..1072.27 rows=947 width=18) (actual time=6.996..63.199 rows=5865 loops=23)" " -> Seq Scan on measurement m (cost=0.00..25.00 rows=6 width=22) (actual time=0.000..0.000 rows=0 loops=23)" " Filter: (m.category_id = 1)" " -> Bitmap Heap Scan on measurement_001 m (cost=20.79..1047.27 rows=941 width=18) (actual time=6.995..62.390 rows=5865 loops=23)" " Recheck Cond: ((m.station_id = sc.station_id) AND (m.taken >= sc.taken_start) AND (m.taken <= sc.taken_end) AND (m.category_id = 1))" " -> Bitmap Index Scan on measurement_001_stc_idx (cost=0.00..20.55 rows=941 width=0) (actual time=5.775..5.775 rows=5865 loops=23)" " Index Cond: ((m.station_id = sc.station_id) AND (m.taken >= sc.taken_start) AND (m.taken <= sc.taken_end) AND (m.category_id = 1))" "Total runtime: 2269.264 ms" 1900 to 1997: Full Table Scan "Sort (cost=1370192.26..1370192.76 rows=200 width=12) (actual time=86165.797..86165.809 rows=94 loops=1)" " Sort Key: (date_part('year'::text, (m.taken)::timestamp without time zone))" " Sort Method: quicksort Memory: 32kB" " -> HashAggregate (cost=1370181.12..1370184.62 rows=200 width=12) (actual time=86165.654..86165.736 rows=94 loops=1)" " -> Hash Join (cost=4293.60..1366355.81 rows=765061 width=12) (actual time=534.786..85920.007 rows=139721 loops=1)" " Hash Cond: (m.station_id = sc.station_id)" " Join Filter: ((m.taken >= sc.taken_start) AND (m.taken <= sc.taken_end))" " -> Append (cost=0.00..867005.80 rows=43670150 width=18) (actual time=0.009..79202.329 rows=43670079 loops=1)" " -> Seq Scan on measurement m (cost=0.00..25.00 rows=6 width=22) (actual time=0.001..0.001 rows=0 loops=1)" " Filter: (category_id = 1)" " -> Seq Scan on measurement_001 m (cost=0.00..866980.80 rows=43670144 width=18) (actual time=0.008..73312.008 rows=43670079 loops=1)" " Filter: (category_id = 1)" " -> Hash (cost=4277.93..4277.93 rows=1253 width=18) (actual time=534.704..534.704 rows=25 loops=1)" " -> Nested Loop (cost=847.87..4277.93 rows=1253 width=18) (actual time=415.837..534.682 rows=25 loops=1)" " Join Filter: ((sec_to_gc(cube_distance((ll_to_earth((c.latitude_decimal)::double precision, (c.longitude_decimal)::double precision))::cube, (ll_to_earth((s.latitude_decimal)::double precision, (s.longitude_decimal)::double precision))::cube)) / 1000::double precision) <= 30::double precision)" " -> Index Scan using city_pkey1 on city c (cost=0.00..2.47 rows=1 width=16) (actual time=0.012..0.014 rows=1 loops=1)" " Index Cond: (id = 5182)" " -> Hash Join (cost=847.87..1352.07 rows=3760 width=34) (actual time=6.427..35.107 rows=3552 loops=1)" " Hash Cond: (s.id = sc.station_id)" " -> Seq Scan on station s (cost=0.00..367.25 rows=7948 width=20) (actual time=0.004..23.529 rows=7949 loops=1)" " Filter: (applicable AND (elevation >= 0) AND (elevation <= 3000))" " -> Hash (cost=800.87..800.87 rows=3760 width=14) (actual time=6.416..6.416 rows=3552 loops=1)" " -> Bitmap Heap Scan on station_category sc (cost=430.29..800.87 rows=3760 width=14) (actual time=2.316..5.353 rows=3552 loops=1)" " Recheck Cond: (category_id = 1)" " Filter: ((taken_start >= '1900-01-01'::date) AND (taken_end <= '1997-12-31'::date))" " -> Bitmap Index Scan on station_category_station_category_idx (cost=0.00..429.35 rows=6376 width=0) (actual time=2.268..2.268 rows=6339 loops=1)" " Index Cond: (category_id = 1)" "Total runtime: 86165.936 ms"

  Read the article

• List of generic algorithms and data structures

  - by Jake Petroules

  As part of a library project, I want to include a plethora of generic algorithms and data structures. This includes algorithms for searching and sorting, data structures like linked lists and binary trees, path-finding algorithms like A*... the works. Basically, any generic algorithm or data structure you can think of that you think might be useful in such a library, please post or add it to the list. Thanks! (NOTE: Because there is no single right answer I've of course placed this in community wiki... and also, please don't suggest algorithms which are too specialized to be provided by a generic library) The List: Data structures AVL tree B-tree B*-tree B+-tree Binary tree Binary heap Binary search tree Linked lists Singly linked list Doubly linked list Stack Queue Sorting algorithms Binary tree sort Bubble sort Heapsort Insertion sort Merge sort Quicksort Selection sort Searching algorithms

  Read the article

• Typical tasks/problems to demonstrate differences between programming languages

  - by Space_C0wb0y

  Somewhere some guy said (I honestly do not know where I got this from), that one should learn one programming language per year. I can see where that might be a good idea, because you learn new patterns and ways to look at the same problems by solving them in different languages. Typically, when learning a new language, I look at how certain problems are supposed to be solved in that language. My question now is, what, in you experience, are good, simple, and clearly defined tasks that demostrate the differences between programming languages. The Idea here is to have a set of tasks, that, when I solve all of them in the language I am learning, gives me a good overview of how things are supposed to be done in that language. I do not know if that is even possible, but it sure would be a useful thing to have. A typical example one often sees especially in tutorials for functional languages is the implementation of quicksort.

  Read the article

• Error in qsort function in Programming Pearls?

  - by Dervin Thunk

  Hello, is it just me or this code in Programming Pearls is wrong (quicksort wants 2 const voids, no?) If so, is my solution right? Apologies, just learning... int wordncmp(char *p, char* q) { int n = k; for ( ; *p == *q; p++, q++) if (*p == 0 && --n == 0) return 0; return *p - *q; } int sortcmp(char **p, char **q) { return wordncmp(*p, *q); } ... qsort(word, nword, sizeof(word[0]), sortcmp); Is this a solution? int sortcmp(const void *p, const void *q) { return wordncmp(* (char * const *) p, * (char * const *) q); }

  Read the article

• Javascript: adding methods using prototype descriptor

  - by LDK

  Sorter.prototype.init_bubblesort = function(){ console.log(this.rect_array); this.end = this.rect_array.length; this.bubblesort(); } Sorter.prototype.init = function(array,sort_type){ this.rect_array = array; this.init_bubblesort(); } The code above works as expected, but when I change the init function to: Sorter.prototype.init = function(array,sort_type){ var sort_types = {'bubblesort':this.init_bubblesort, 'quicksort':this.init_quicksort, 'liamsort':this.init_liamsort}; this.rect_array = array; sort_types[sort_type](); } the init_bubblesort function results in an error saying this.rect_array is undefined. I'm trying to wrap my head around why init_bubblesort no longer as access to it's instance's variables.

  Read the article

• A way to use Python which I don't know

  - by Konie

  In this quicksort function: def qsort2(list): if list == []: return [] else: pivot = list[0] # can't understand the following line lesser, equal, greater = partition(list[1:], [], [pivot], []) return qsort2(lesser) + equal + qsort2(greater) def partition(list, l, e, g): if list == []: return (l, e, g) else: head = list[0] if head < e[0]: return partition(list[1:], l + [head], e, g) elif head > e[0]: return partition(list[1:], l, e, g + [head]) else: return partition(list[1:], l, e + [head], g) I don't understand the sentence below the comment. Can someone tell me what is the meaning of this sentence here?

  Read the article

• Is there an appropriate coding style for implementing an algorithm during an interview?

  - by GlenPeterson

  I failed an interview question in C years ago about converting hex to decimal by not exploiting the ASCII table if (inputDigitByte > 9) hex = inputDigitByte - 'a'. The rise of Unicode has made this question pretty silly, but the point was that the interviewer valued raw execution speed above readability and error handling. They tell you to review algorithms textbooks to prepare for these interviews, yet these same textbooks tend to favor the implementation with the fewest lines of code, even if it has to rely on magic numbers (like "infinity") and a slower, more memory-intensive implementation (like a linked list instead of an array) to do that. I don't know what is right. Coding an algorithm within the space of an interview has at least 3 constraints: time to code, elegance/readability, and efficiency of execution. What trade-offs are appropriate for interview code? How much do you follow the textbook definition of an algorithm? Is it better to eliminate recursion, unroll loops, and use arrays for efficiency? Or is it better to use recursion and special values like "infinity" or Integer.MAX_VALUE to reduce the number of lines of code needed to write the algorithm? Interface: Make a very self-contained, bullet-proof interface, or sloppy and fast? On the one extreme, the array to be sorted might be a public static variable. On the other extreme, it might need to be passed to each method, allowing methods to be called individually from different threads for different purposes. Is it appropriate to use a linked-list data structure for items that are traversed in one direction vs. using arrays and doubling the size when the array is full? Implementing a singly-linked list during the interview is often much faster to code and easier remember for recursive algorithms like MergeSort. Thread safety - just document that it's unsafe, or say so verbally? How much should the interviewee be looking for opportunities for parallel processing? Is bit shifting appropriate? x / 2 or x >> 1 Polymorphism, type safety, and generics? Comments? Variable and method names: qs(a, p, q, r) vs: quickSort(theArray, minIdx, partIdx, maxIdx) How much should you use existing APIs? Obviously you can't use a java.util.HashMap to implement a hash-table, but what about using a java.util.List to accumulate your sorted results? Are there any guiding principals that would answer these and other questions, or is the guiding principal to ask the interviewer? Or maybe this should be the basis of a discussion while writing the code? If an interviewer can't or won't answer one of these questions, are there any tips for coaxing the information out of them?

  Read the article

• Finding work as a college student

  - by lightburst

  I'm a 3rd year CS student. I'm currently really, really, bored and tired of cheap school programming(I go to a fairly respectable(albeit not top) university in my country, but, really, it's not MIT) so I've been thinking about getting a part-time dev job for a long while now. I'm not some hotshot programmer or anything, but "Add/Delete XYZ class objects to list" or "Do this web feature/pattern in PHP" does get old after a few semesters. I also only learned(heard?) of programming when I entered college, so the duration of me being in contact with any code is short. I can't really apply as an intern as I have not accumulated the necessary credits yet to do that so I was thinking of selling myself as a part-time dev. I still need to go to school, and don't want to subject myself to living two lives. Plus, I think I'd have better chances considering my lack of things to write on the resume. The only language I know at heart is C (I've written several pointer-oriented stuff on my freshman year, which is apparently pretty leet(for some reason), or so Joel says. That sort of boosted my morale a bit) but I've worked with several other languages only for the sake of course work such as C#/Java/PHP/ASM. My only user-worthy project was a recursive quicksort simulator I wrote for class using GTK+ that used a textbox to output the progress. I also have not taken the compiler theory class yet, or my thesis. All that being said, I wonder if any legitimate software company(big or small) would hire somebody like me considering all that. If there are companies that do accept anybody like me, would I be doing programming or maybe just be a tester or something? Would anybody hire me as a dev at all? I know I don't have much(not even a degree) but what I lack in experience, I compensate with interest? I am less interested in websites and 'management' software(no offense or anything. also, most of the places here ONLY have those), and more into 'process driven'(I'm not sure how to call it) and system software. I have my eyes on a startup that sells basically an extension of Google Drive, but I feel like I'm too 'risky' for them. Oh, I'm also 19 if that means anything. We're not K-12 so kids go to college earlier than in the US.

  Read the article

• Any tips on getting hired as a software project manager straight out of college?

  - by MHarrison

  I graduated with a BS in compsci last September, and I've been trying (unsuccessfully) to find a job as a project manager ever since. I fell in love with software engineering (the formal practice behind it all, not just coding) in school, and I've dedicated the last 3-4 years of my life to learning everything I can about project management and gaining experience. I've managed several projects (with teams around 12 people) while in school, and I worked with my university's software engineering research lab. My résumé is also decent - I worked as a programmer before I went to school (I'm 27 now), and I did Google Summer of Code for 3 summers. I also have general "people management" experience via working as the photo editor for my university's newspaper for 2 years. My first problem with the job hunt is not getting enough interviews. I use careers.stackoverflow.com, which is awesome because I usually get contacted by non-HR people who know what they're talking about, but there's just not enough companies using it for me to get interviews on a regular basis. I've also tried sites like monster.com, and in a fit of desperation, I sent out no less than 60 applications to project management positions. I've gotten 3 automated rejection letters and that's it. At least careers.stackoverflow gets me a phone interview with 8/10 places I apply to. But the main (and extremely frustrating) problem is the matter of experience. I've successfully managed projects from start to finish (in my software engineering classes we had real customers come in with a real software need and we built it for them), but I've never had to deal with budgets and money (I know this is why HR people immediately turn me away). Most of these positions require 5+ years PM experience, and I've seen absurd things like 12+ years required. Interviews are also maddening. I've had so many places who absolutely loved me and I made it to the final round of interviews, and I left thinking things went extremely well and they'd consider me. However, when I check in with them a week later, they tell me "We really liked you and your qualifications are excellent, but we're hoping to find someone with more experience." The bad interviews I can understand - like the PM position that would have had me managing developers both locally and overseas - I had 3 interviews with them and the ENTIRE interview process was them asking me CS brainteasers and having me waste time on things like writing quicksort on paper or writing binary search trees. Even when I tried steering the discussion towards more relevant PM stuff, they gave me some vague generic replies and went back to the "We want to be Google/MS" crap. But when I have a GOOD interview, they say my "qualifications are excellent" but they want "more experience"...that makes me want to tear my hair out. What else can I DO? While I'm aiming for technically-involved PM positions (not just crunching budget numbers), I really don't want a straight development job because I like creating software from the very high-level vs. spending a lot of time debugging memory leaks. In fact, I can't even GET development positions that I'm qualified for because I make the mistake of telling them that my future career goals are as PM (which usually results in them saying something like "Well we already have PMs and this position isn't really set up to get you there." - which I take to mean "No, that's my job, stay away.") My apologies on the long rant, but I'm seriously hellbent on getting hired as a PM since it's both my career goal and the passion that keeps me awake at night. Any suggestions on what the heck else I can do? I'm currently writing a blog where I talk about my philosophies about software engineering, and I'm writing up specs for an iOS app which I will design, code, and show employers, but this takes an awful lot of time that I don't have.

  Read the article

• What's the "best" database for embedded?

  - by mawg

  I'm an embedded guy, not a database guy. I've been asked to redesign an existing system which has bottlenecks in several places. The embedded device is based around an ARM 9 processor running at 220mHz. There should be a database of 50k entries (may increase to 250k) each with 1k of data (max 8 filed). That's approximate - I can try to get more precise figures if necessary. They are currently using SqlLite 2 and planning to move to SqlLite 3. Without starting a flame war - I am a complete d/b newbie just seeking advice - is that the "best" decision? I realize that this might be a "how long is a piece of string?" question, but any pointers woudl be greatly welcomed. I don't mind doing a lot of reading & research, but just hoped that you could get me off to a flying start. Thanks. p.s Again, a total rewrite, might not even stick with embedded Linux, but switch to eCos, don't worry too much about one time conversion between d/b formats. Oh, and accesses should be infrequent, at most one every few seconds. edit: ok, it seems they have 30k entries (may reach 100k or more) of only 5 or 6 fields each, but at least 3 of them can be a search key for a record. They are toying with "having no d/b at all, since the data are so simple", but it seems to me that with multiple keys, we couldn't use fancy stuff like a quicksort() type search (recursive, binary search). Any thoughts on "no d/b", just data-structures? Btw, one key is 800k - not sure how well SqlLite handles that (maybe with "no d/b" I have to hash that 800k to something smaller?)

  Read the article

• How would the 'Model' in a Rails-type webapp be implemented in a functional programming langauge?

  - by ceptorial

  In MVC web development frameworks such as Ruby on Rails, Django, and CakePHP, HTTP requests are routed to controllers, which fetch objects which are usually persisted to a backend database store. These objects represent things like users, blog posts, etc., and often contain logic within their methods for permissions, fetching and/or mutating other objects, validation, etc. These frameworks are all very much object oriented. I've been reading up recently on functional programming and it seems to tout tremendous benefits such as testability, conciseness, modularity, etc. However most of the examples I've seen for functional programming implement trivial functionality like quicksort or the fibonnacci sequence, not complex webapps. I've looked at a few 'functional' web frameworks, and they all seem to implement the view and controller just fine, but largely skip over the whole 'model' and 'persistence' part. (I'm talking more about frameworks like Compojure which are supposed to be purely functional, versus something Lift which conveniently seems to use the OO part of Scala for the model -- but correct me if I'm wrong here.) I haven't seen a good explanation of how functional programming can be used to provide the metaphor that OO programming provides, i.e. tables map to objects, and objects can have methods which provide powerful, encapsulated logic such as permissioning and validation. Also the whole concept of using SQL queries to persist data seems to violate the whole 'side effects' concept. Could someone provide an explanation of how the 'model' layer would be implemented in a functionally programmed web framework?

  Read the article

• sort outer array based on values in inner array, javascript

  - by ptrn

  I have an array with arrays in it, where I want to sort the outer arrays based on values in a specific column in the inner. I bet that sounded more than a bit confusing, so I'll skip straight to an example. Initial data: var data = [ [ "row_1-col1", "2-row_1-col2", "c-row_1-coln" ], [ "row_2-col1", "1-row_2-col2", "b-row_2-coln" ], [ "row_m-col1", "3-row_m-col2", "a-row_m-coln" ] ]; Sort data, based on column with index 1 data.sortFuncOfSomeKind(1); where the object then would look like this; var data = [ [ "row_2-col1", "1-row_2-col2", "b-row_2-coln" ], [ "row_1-col1", "2-row_1-col2", "c-row_1-coln" ], [ "row_m-col1", "3-row_m-col2", "a-row_m-coln" ] ]; Sort data, based on column with index 2 data.sortFuncOfSomeKind(2); where the object then would look like this; var data = [ [ "row_m-col1", "3-row_m-col2", "a-row_m-coln" ], [ "row_2-col1", "1-row_2-col2", "b-row_2-coln" ], [ "row_1-col1", "2-row_1-col2", "c-row_1-coln" ] ]; The big Q Is there an existing solution to this that you know of, or would I have to write one myself? If so, which would be the easiest sort algorithm to use? QuickSort? _L

  Read the article

• algorithm - How to sort a 0/1 array with 2n/3 comparisons?

  - by Jackson Tale

  In Algorithm Design Manual, there is such an excise 4-26 Consider the problem of sorting a sequence of n 0’s and 1’s using comparisons. For each comparison of two values x and y, the algorithm learns which of x < y, x = y, or x y holds. (a) Give an algorithm to sort in n - 1 comparisons in the worst case. Show that your algorithm is optimal. (b) Give an algorithm to sort in 2n/3 comparisons in the average case (assuming each of the n inputs is 0 or 1 with equal probability). Show that your algorithm is optimal. For (a), I think it is fairly easy. I can choose a[n-1] as pivot, then do something like in quicksort partition, scan 0 to n - 2, find the middle point where left side is all 0 and right side is all 1, this take n - 1 comparisons. But for (b), I can't get a clue. It says "each of the n inputs is 0 or 1 with equal probability", so I guess I can assume the numbers of 0 and 1 equal? But how can I get a result which is related to 1/3? divide the whole array into 3 groups? Thanks

  Read the article

• how does MySQL implement the "group by"?

  - by user188916

  I read from the MySQL Reference Manual and find that when it can take use of index,it just do index scan,other it will create tmp tables and do things like filesort. And I also read from other article that the "Group By" result will sort by group by columns by default,if "order by null" clause added,it won't don filesort. The difference can be found from the "explain ..." clause. so my problem is:what is the difference between "group by" clause that with "order by null" and which doesn't have? I try to use profiling to see what mysql do on the background,and only see result like: result for group clause without order by null: |preparing | 0.000016 | | Creating tmp table | 0.000048 | | executing | 0.000009 | | Copying to tmp table | 0.000109 | **| Sorting result | 0.000023 |** | Sending data | 0.000027 | result for clause with "order by null": preparing | 0.000016 | | Creating tmp table | 0.000052 | | executing | 0.000009 | | Copying to tmp table | 0.000114 | | Sending data | 0.000028 | So I guess what MySQL do when the "order by null" added,it does not use filesort algorithm,maybe when it creates the tmp table,it uses index as well,and then use the index to do group by operation,when completed,it just read result from the table rows and does not sort the result. But my original opinion is that MySQL can use quicksort to sort the items and then do group by,so the result will be sorted as well. Any opinion appreciated,thanks.

  Read the article

• Interview question: C program to sort a binary array in O(n)

  - by Zacky112

  I've comeup with the following program to do it, but it does not seem to work and goes into infinite loop. Its working is similar to quicksort. int main() { int arr[] = {1,1,0,1,0,0,0,1,0,1,0,1,0,1,0,1,0,1}; int N = 18; int *front, *last; front = arr; last = arr + N; while(front <= last) { while( (front < last) && (*front == 0) ) front++; while( (front < last) && (*last == 1) ) last--; if( front < last) { int temp = *front; *front = *last; *last = temp; front ++; last--; } } for(int i=0;i<N;i++) printf("%d ",arr[i]); return 0; }

  Read the article

• Given a vector of maximum 10 000 natural and distinct numbers, find 4 numbers(a, b, c, d) such that

  - by king_kong

  Hi, I solved this problem by following a straightforward but not optimal algorithm. I sorted the vector in descending order and after that substracted numbers from max to min to see if I get a + b + c = d. Notice that I haven't used anywhere the fact that elements are natural, distinct and 10 000 at most. I suppose these details are the key. Does anyone here have a hint over an optimal way of solving this? Thank you in advance! Later Edit: My idea goes like this: '<<quicksort in descending order>>' for i:=0 to count { // after sorting, loop through the array int d := v[i]; for j:=i+1 to count { int dif1 := d - v[j]; int a := v[j]; for k:=j+1 to count { if (v[k] > dif1) continue; int dif2 := dif1 - v[k]; b := v[k]; for l:=k+1 to count { if (dif2 = v[l]) { c := dif2; return {a, b, c, d} } } } } } What do you think?(sorry for the bad indentation)

  Read the article

• Read variable-length records from a buffer - weird memory issues

  - by bsg

  Hi, I'm trying to implement an i/o intensive quicksort (C++ qsort) on a very large dataset. In the interests of speed, I'd like to read in a chunk of data at a time into a buffer and then use qsort to sort it inside the buffer. (I am currently working with text files but would like to move to binary soon.) However, my data is composed of variable-length records, and qsort needs to be told the length of the record in order to sort. Is there any way to standardize this? The only thing I could think of was rather convoluted: my program currently reads from the buffer until it hits a linefeed character ('10' in ascii), transferring each character over to another array. When it finds a linefeed (the delimiter in the input file), it fills the number of spaces remaining in the buffer for that record (record size is set to 30) with null characters. This way, I should end up with a buffer full of fixed-size records to give qsort. I know there are several problems with my approach, one being that it's just clumsy, another that the record size might conceivably be larger than 30, but is generally much less. Is there a better way of doing this? As well, my current code doesn't even work. When I debug it, it seems to be transferring characters from one buffer to the other, but when I try to print out the buffer, it contains only the first record. Here is my code: FILE *fp; unsigned char *buff; unsigned char *realbuff; FILE *inputFiles[NUM_INPUT_FILES]; buff = (unsigned char *) malloc(2048); realbuff = (unsigned char *) malloc(NUM_RECORDS * RECORD_SIZE); fp = fopen("postings0.txt", "r"); if(fp) { fread(buff, 1, 2048, fp); /*for(int i=0; i <30; i++) cout << buff[i] <<endl;*/ int y=0; int recordcounter = 0; //cout << buff; for(int i=0;i <100; i++) { if(buff[i] != char(10)) { realbuff[y] = buff[i]; y++; recordcounter++; } else { if(recordcounter < RECORD_SIZE) for(int j=recordcounter; j < RECORD_SIZE;j++) { realbuff[y] = char(0); y++; } recordcounter = 0; } } cout << realbuff <<endl; cout << buff; } else cout << "sorry"; Thank you very much, bsg

  Read the article

• Unexpected output from Bubblesort program with MSVC vs TCC

  - by Sujith S Pillai

  One of my friends sent this code to me, saying it doesn't work as expected: #include<stdio.h> void main() { int a [10] ={23, 100, 20, 30, 25, 45, 40, 55, 43, 42}; int sizeOfInput = sizeof(a)/sizeof(int); int b, outer, inner, c; printf("Size is : %d \n", sizeOfInput); printf("Values before bubble sort are : \n"); for ( b = 0; b &lt; sizeOfInput; b++) printf("%d\n", a[b]); printf("End of values before bubble sort... \n"); for ( outer = sizeOfInput; outer &gt; 0; outer-- ) { for ( inner = 0 ; inner &lt; outer ; inner++) { printf ( "Comparing positions: %d and %d\n",inner,inner+1); if ( a[inner] &gt; a[inner + 1] ) { int tmp = a[inner]; a[inner] = a [inner+1]; a[inner+1] = tmp; } } printf ( "Bubble sort total array size after inner loop is %d :\n",sizeOfInput); printf ( "Bubble sort sizeOfInput after inner loop is %d :\n",sizeOfInput); } printf ( "Bubble sort total array size at the end is %d :\n",sizeOfInput); for ( c = 0 ; c &lt; sizeOfInput; c++) printf("Element: %d\n", a[c]); } I am using Micosoft Visual Studio Command Line Tool for compiling this on a Windows XP machine. cl /EHsc bubblesort01.c My friend gets the correct output on a dinosaur machine (code is compiled using TCC there). My output is unexpected. The array mysteriously grows in size, in between. If you change the code so that the variable sizeOfInput is changed to sizeOfInputt, it gives the expected results! A search done at Microsoft Visual C++ Developer Center doesn't give any results for "sizeOfInput". I am not a C/C++ expert, and am curious to find out why this happens - any C/C++ experts who can "shed some light" on this? Unrelated note: I seriously thought of rewriting the whole code to use quicksort or merge sort before posting it here. But, after all, it is not Stooge sort... Edit: I know the code is not correct (it reads beyond the last element), but I am curious why the variable name makes a difference.

  Read the article

• Parsing language for both binary and character files

  - by Thorsten S.

  The problem: You have some data and your program needs specified input. For example strings which are numbers. You are searching for a way to transform the original data in a format you need. And the problem is: The source can be anything. It can be XML, property lists, binary which contains the needed data deeply embedded in binary junk. And your output format may vary also: It can be number strings, float, doubles.... You don't want to program. You want routines which gives you commands capable to transform the data in a form you wish. Surely it contains regular expressions, but it is very good designed and it offers capabilities which are sometimes much more easier and more powerful. Something like a super-grep which you can access (!) as program routines, not only as tool. It allows: joining/grouping/merging of results inserting/deleting/finding/replacing write macros which allows to execute a command chain repeatedly meta-grouping (lists-tables-hypertables) Example (No, I am not looking for a solution to this, it is just an example): You want to read xml strings embedded in a binary file with variable length records. Your tool reads the record length and deletes the junk surrounding your text. Now it splits open the xml and extracts the strings. Being Indian number glyphs and containing decimal commas instead of decimal points, your tool transforms it into ASCII and replaces commas with points. Now the results must be stored into matrices of variable length....etc. etc. I am searching for a good language / language-design and if possible, an implementation. Which design do you like or even, if it does not fulfill the conditions, wouldn't you want to miss ? EDIT: The question is if a solution for the problem exists and if yes, which implementations are available. You DO NOT implement your own sorting algorithm if Quicksort, Mergesort and Heapsort is available. You DO NOT invent your own text parsing method if you have regular expressions. You DO NOT invent your own 3D language for graphics if OpenGL/Direct3D is available. There are existing solutions or at least papers describing the problem and giving suggestions. And there are people who may have worked and experienced such problems and who can give ideas and suggestions. The idea that this problem is totally new and I should work out and implement it myself without background knowledge seems for me, I must admit, totally off the mark.

  Read the article

• Unexpected output while using Microsoft Visual Studio 2008 (Express Edition) C++ Command Line Tool

  - by Sujith S Pillai

  One of my friends sent this code to me, saying it doesn't work as expected: #include<stdio.h> void main() { int a [10] ={23, 100, 20, 30, 25, 45, 40, 55, 43, 42}; int sizeOfInput = sizeof(a)/sizeof(int); int b, outer, inner, c; printf("Size is : %d \n", sizeOfInput); printf("Values before bubble sort are : \n"); for ( b = 0; b < sizeOfInput; b++) printf("%d\n", a[b]); printf("End of values before bubble sort... \n"); for ( outer = sizeOfInput; outer > 0; outer-- ) { for ( inner = 0 ; inner < outer ; inner++) { printf ( "Comparing positions: %d and %d\n",inner,inner+1); if ( a[inner] > a[inner + 1] ) { int tmp = a[inner]; a[inner] = a [inner+1]; a[inner+1] = tmp; } } printf ( "Bubble sort total array size after inner loop is %d :\n",sizeOfInput); printf ( "Bubble sort sizeOfInput after inner loop is %d :\n",sizeOfInput); } printf ( "Bubble sort total array size at the end is %d :\n",sizeOfInput); for ( c = 0 ; c < sizeOfInput; c++) printf("Element: %d\n", a[c]); } I am using Micosoft Visual Studio Command Line Tool for compiling this on a Windows XP machine. cl /EHsc bubblesort01.c My friend gets the correct output on a dinosaur machine (code is compiled using TCC there). My output is unexpected. The array mysteriously grows in size, in between. If you change the code so that the variable sizeOfInput is changed to sizeOfInputt, it gives the expected results! A search done at Microsoft Visual C++ Developer Center doesn't give any results for "sizeOfInput". I am not a C/C++ expert, and am curious to find out why this happens - any C/C++ experts who can "shed some light" on this? Unrelated note: I seriously thought of rewriting the whole code to use quicksort or merge sort before posting it here. But, after all, it is not Stooge sort...

  Read the article

• Java invalid stream header Problem

  - by David zsl

  Hi all, im writen a client-server app, and now i´m facing a problem that I dont know how to solve: This is the client: try { Socket socket = new Socket(ip, port); ObjectOutputStream ooos = new ObjectOutputStream(socket .getOutputStream()); SendMessage message = new SendMessage(); message.numDoc = value.numDoc; message.docFreq = value.docFreq; message.queryTerms = query; message.startIndex = startIndex; message.count = count; message.multiple = false; message.ips = null; message.ports = null; message.value = true; message.docFreq = value.docFreq; message.numDoc = value.numDoc; ooos.writeObject(message); ObjectInputStream ois = new ObjectInputStream(socket .getInputStream()); ComConstants mensajeRecibido; Object mensajeAux; String mensa = null; byte[] by = null; do { mensajeAux = ois.readObject(); if (mensajeAux instanceof ComConstants) { System.out.println("Thread by Thread has Search Results"); String test; ByteArrayOutputStream testo = new ByteArrayOutputStream(); mensajeRecibido = (ComConstants) mensajeAux; byte[] wag; testo.write( mensajeRecibido.fileContent, 0, mensajeRecibido.okBytes); wag = testo.toByteArray(); if (by == null) { by = wag; } else { int size = wag.length; System.arraycopy(wag, 0, by, 0, size); } } else { System.err.println("Mensaje no esperado " + mensajeAux.getClass().getName()); break; } } while (!mensajeRecibido.lastMessage); //ByteArrayInputStream bs = new ByteArrayInputStream(by.toByteArray()); // bytes es el byte[] ByteArrayInputStream bs = new ByteArrayInputStream(by); ObjectInputStream is = new ObjectInputStream(bs); QueryWithResult[] unObjetoSerializable = (QueryWithResult[])is.readObject(); is.close(); //AQUI TOCARIA METER EL QUICKSORT XmlConverter xce = new XmlConverter(unObjetoSerializable, startIndex, count); String serializedd = xce.runConverter(); tempFinal = serializedd; ois.close(); socket.close(); } catch (Exception e) { e.printStackTrace(); } i++; } And this is the sender: try { QueryWithResult[] outputLine; Operations op = new Operations(); boolean enviadoUltimo=false; ComConstants mensaje = new ComConstants(); mensaje.queryTerms = query; outputLine = op.processInput(query, value); //String c = new String(); //c = outputLine.toString(); //StringBuffer swa = sw.getBuffer(); ByteArrayOutputStream bs= new ByteArrayOutputStream(); ObjectOutputStream os = new ObjectOutputStream (bs); os.writeObject(outputLine); os.close(); byte[] mybytearray = bs.toByteArray(); ByteArrayInputStream byteArrayInputStream = new ByteArrayInputStream(mybytearray); BufferedInputStream bis = new BufferedInputStream(byteArrayInputStream); int readed = bis.read(mensaje.fileContent,0,4000); while (readed > -1) { mensaje.okBytes = readed; if (readed < ComConstants.MAX_LENGTH) { mensaje.lastMessage = true; enviadoUltimo=true; } else mensaje.lastMessage = false; oos.writeObject(mensaje); if (mensaje.lastMessage) break; mensaje = new ComConstants(); mensaje.queryTerms = query; readed = bis.read(mensaje.fileContent); } if (enviadoUltimo==false) { mensaje.lastMessage=true; mensaje.okBytes=0; oos.writeObject(mensaje); } oos.close(); } catch (Exception e) { e.printStackTrace(); } } And this is the error log: Thread by Thread has Search Results java.io.StreamCorruptedException: invalid stream header: 20646520 at java.io.ObjectInputStream.readStreamHeader(Unknown Source) at java.io.ObjectInputStream.<init>(Unknown Source) at org.tockit.comunication.ServerThread.enviaFicheroMultiple(ServerThread.java:747) at org.tockit.comunication.ServerThread.run(ServerThread.java:129) at java.lang.Thread.run(Unknown Source) Where at org.tockit.comunication.ServerThread.enviaFicheroMultiple(ServerThread.java:747) is this line ObjectInputStream is = new ObjectInputStream(bs); on the 1st code just after while (!mensajeRecibido.lastMessage); Any ideas?

  Read the article

• Having trouble returning a value from a method call when sending an array and the program is error out when run in reference to the sort

  - by programmerNOOB

  I am getting the following output when this program is run: Please enter the Social Security Number for taxpayer 0: 111111111 Please enter the gross income for taxpayer 0: 20000 Please enter the Social Security Number for taxpayer 1: 555555555 Please enter the gross income for taxpayer 1: 50000 Please enter the Social Security Number for taxpayer 2: 333333333 Please enter the gross income for taxpayer 2: 5464166 Please enter the Social Security Number for taxpayer 3: 222222222 Please enter the gross income for taxpayer 3: 645641 Please enter the Social Security Number for taxpayer 4: 444444444 Please enter the gross income for taxpayer 4: 29000 Taxpayer # 1 SSN: 111111111, Income is $20,000.00, Tax is $0.00 Taxpayer # 2 SSN: 555555555, Income is $50,000.00, Tax is $0.00 Taxpayer # 3 SSN: 333333333, Income is $5,464,166.00, Tax is $0.00 Taxpayer # 4 SSN: 222222222, Income is $645,641.00, Tax is $0.00 Taxpayer # 5 SSN: 444444444, Income is $29,000.00, Tax is $0.00 Unhandled Exception: System.InvalidOperationException: Failed to compare two elements in the array. --- System.ArgumentException: At least one object must implement IComparable. at System.Collections.Comparer.Compare(Object a, Object b) at System.Collections.Generic.ObjectComparer`1.Compare(T x, T y) at System.Collections.Generic.ArraySortHelper`1.SwapIfGreaterWithItems(T[] keys, IComparer`1 comparer, Int32 a, Int32 b) at System.Collections.Generic.ArraySortHelper`1.QuickSort(T[] keys, Int32 left, Int32 right, IComparer`1 comparer) at System.Collections.Generic.ArraySortHelper`1.Sort(T[] keys, Int32 index, Int32 length, IComparer`1 comparer) --- End of inner exception stack trace --- at System.Collections.Generic.ArraySortHelper`1.Sort(T[] keys, Int32 index, Int32 length, IComparer`1 comparer) at System.Array.Sort[T](T[] array, Int32 index, Int32 length, IComparer`1 comparer) at System.Array.Sort[T](T[] array) at Assignment5.Taxpayer.Main(String[] args) in Program.cs:line 150 Notice the 0s at the end of the line that should be the tax amount??? Here is the code: using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace taxes { class Rates { // Create a class named rates that has the following data members: private int incLimit; private double lowTaxRate; private double highTaxRate; // use read-only accessor public int IncomeLimit { get { return incLimit; } } public double LowTaxRate { get { return lowTaxRate; } } public double HighTaxRate { get { return highTaxRate; } } //A class constructor that assigns default values public Rates() { int limit = 30000; double lowRate = .15; double highRate = .28; incLimit = limit; lowTaxRate = lowRate; highTaxRate = highRate; } //A class constructor that takes three parameters to assign input values for limit, low rate and high rate. public Rates(int limit, double lowRate, double highRate) { } // A CalculateTax method that takes an income parameter and computes the tax as follows: public int CalculateTax(int income) { int limit = 0; double lowRate = 0; double highRate = 0; int taxOwed = 0; // If income is less than the limit then return the tax as income times low rate. if (income < limit) taxOwed = Convert.ToInt32(income * lowRate); // If income is greater than or equal to the limit then return the tax as income times high rate. if (income >= limit) taxOwed = Convert.ToInt32(income * highRate); return taxOwed; } } //end class Rates // Create a class named Taxpayer that has the following data members: public class Taxpayer { //Use get and set accessors. string SSN { get; set; } int grossIncome { get; set; } // Use read-only accessor. public int taxOwed { get { return taxOwed; } } // The Taxpayer class should be set up so that its objects are comparable to each other based on tax owed. class taxpayer : IComparable { public int taxOwed { get; set; } public int income { get; set; } int IComparable.CompareTo(Object o) { int returnVal; taxpayer temp = (taxpayer)o; if (this.taxOwed > temp.taxOwed) returnVal = 1; else if (this.taxOwed < temp.taxOwed) returnVal = -1; else returnVal = 0; return returnVal; } // End IComparable.CompareTo } //end taxpayer IComparable class // **The tax should be calculated whenever the income is set. // The Taxpayer class should have a getRates class method that has the following. public static void GetRates() { // Local method data members for income limit, low rate and high rate. int incLimit = 0; double lowRate; double highRate; string userInput; // Prompt the user to enter a selection for either default settings or user input of settings. Console.Write("Would you like the default values (D) or would you like to enter the values (E)?: "); /* If the user selects default the default values you will instantiate a rates object using the default constructor * and set the Taxpayer class data member for tax equal to the value returned from calling the rates object CalculateTax method.*/ userInput = Convert.ToString(Console.ReadLine()); if (userInput == "D" || userInput == "d") { Rates rates = new Rates(); rates.CalculateTax(incLimit); } // end if /* If the user selects to enter the rates data then prompt the user to enter values for income limit, low rate and high rate, * instantiate a rates object using the three-argument constructor passing those three entries as the constructor arguments and * set the Taxpayer class data member for tax equal to the valuereturned from calling the rates object CalculateTax method. */ if (userInput == "E" || userInput == "e") { Console.Write("Please enter the income limit: "); incLimit = Convert.ToInt32(Console.ReadLine()); Console.Write("Please enter the low rate: "); lowRate = Convert.ToDouble(Console.ReadLine()); Console.Write("Please enter the high rate: "); highRate = Convert.ToDouble(Console.ReadLine()); Rates rates = new Rates(incLimit, lowRate, highRate); rates.CalculateTax(incLimit); } } static void Main(string[] args) { Taxpayer[] taxArray = new Taxpayer[5]; Rates taxRates = new Rates(); // Implement a for-loop that will prompt the user to enter the Social Security Number and gross income. for (int x = 0; x < taxArray.Length; ++x) { taxArray[x] = new Taxpayer(); Console.Write("Please enter the Social Security Number for taxpayer {0}: ", x + 1); taxArray[x].SSN = Console.ReadLine(); Console.Write("Please enter the gross income for taxpayer {0}: ", x + 1); taxArray[x].grossIncome = Convert.ToInt32(Console.ReadLine()); } Taxpayer.GetRates(); // Implement a for-loop that will display each object as formatted taxpayer SSN, income and calculated tax. for (int i = 0; i < taxArray.Length; ++i) { Console.WriteLine("Taxpayer # {0} SSN: {1}, Income is {2:c}, Tax is {3:c}", i + 1, taxArray[i].SSN, taxArray[i].grossIncome, taxRates.CalculateTax(taxArray[i].grossIncome)); } // end for // Implement a for-loop that will sort the five objects in order by the amount of tax owed Array.Sort(taxArray); Console.WriteLine("Sorted by tax owed"); for (int i = 0; i < taxArray.Length; ++i) { Console.WriteLine("Taxpayer # {0} SSN: {1}, Income is {2:c}, Tax is {3:c}", i + 1, taxArray[i].SSN, taxArray[i].grossIncome, taxRates.CalculateTax(taxArray[i].grossIncome)); } } //end main } // end Taxpayer class } //end Any clues as to why the dollar amount is coming up as 0 and why the sort is not working?

  Read the article

• Mulitple full joins in Postgres is slow

  - by blast83

  I have a program to use the IMDB database and am having very slow performance on my query. It appears that it doesn't use my where condition until after it materializes everything. I looked around for hints to use but nothing seems to work. Here is my query: SELECT * FROM name as n1 FULL JOIN aka_name ON n1.id = aka_name.person_id FULL JOIN cast_info as t2 ON n1.id = t2.person_id FULL JOIN person_info as t3 ON n1.id = t3.person_id FULL JOIN char_name as t4 ON t2.person_role_id = t4.id FULL JOIN role_type as t5 ON t2.role_id = t5.id FULL JOIN title as t6 ON t2.movie_id = t6.id FULL JOIN aka_title as t7 ON t6.id = t7.movie_id FULL JOIN complete_cast as t8 ON t6.id = t8.movie_id FULL JOIN kind_type as t9 ON t6.kind_id = t9.id FULL JOIN movie_companies as t10 ON t6.id = t10.movie_id FULL JOIN movie_info as t11 ON t6.id = t11.movie_id FULL JOIN movie_info_idx as t19 ON t6.id = t19.movie_id FULL JOIN movie_keyword as t12 ON t6.id = t12.movie_id FULL JOIN movie_link as t13 ON t6.id = t13.linked_movie_id FULL JOIN link_type as t14 ON t13.link_type_id = t14.id FULL JOIN keyword as t15 ON t12.keyword_id = t15.id FULL JOIN company_name as t16 ON t10.company_id = t16.id FULL JOIN company_type as t17 ON t10.company_type_id = t17.id FULL JOIN comp_cast_type as t18 ON t8.status_id = t18.id WHERE n1.id = 2003 Very table is related to each other on the join via foreign-key constraints and have indexes for all the mentioned columns. The query plan details: "Hash Left Join (cost=5838187.01..13756845.07 rows=15579622 width=835) (actual time=146879.213..146891.861 rows=20 loops=1)" " Hash Cond: (t8.status_id = t18.id)" " -> Hash Left Join (cost=5838185.92..13542624.18 rows=15579622 width=822) (actual time=146879.199..146891.833 rows=20 loops=1)" " Hash Cond: (t10.company_type_id = t17.id)" " -> Hash Left Join (cost=5838184.83..13328403.29 rows=15579622 width=797) (actual time=146879.165..146891.781 rows=20 loops=1)" " Hash Cond: (t10.company_id = t16.id)" " -> Hash Left Join (cost=5828372.95..10061752.03 rows=15579622 width=755) (actual time=146426.483..146429.756 rows=20 loops=1)" " Hash Cond: (t12.keyword_id = t15.id)" " -> Hash Left Join (cost=5825164.23..6914088.45 rows=15579622 width=731) (actual time=146372.411..146372.529 rows=20 loops=1)" " Hash Cond: (t13.link_type_id = t14.id)" " -> Merge Left Join (cost=5825162.82..6699867.24 rows=15579622 width=715) (actual time=146372.366..146372.472 rows=20 loops=1)" " Merge Cond: (t6.id = t13.linked_movie_id)" " -> Merge Left Join (cost=5684009.29..6378956.77 rows=15579622 width=699) (actual time=144019.620..144019.711 rows=20 loops=1)" " Merge Cond: (t6.id = t12.movie_id)" " -> Merge Left Join (cost=5182403.90..5622400.75 rows=8502523 width=687) (actual time=136849.731..136849.809 rows=20 loops=1)" " Merge Cond: (t6.id = t19.movie_id)" " -> Merge Left Join (cost=4974472.00..5315778.48 rows=8502523 width=637) (actual time=134972.032..134972.099 rows=20 loops=1)" " Merge Cond: (t6.id = t11.movie_id)" " -> Merge Left Join (cost=1830064.81..2033131.89 rows=1341632 width=561) (actual time=63784.035..63784.062 rows=2 loops=1)" " Merge Cond: (t6.id = t10.movie_id)" " -> Nested Loop Left Join (cost=1417360.29..1594294.02 rows=1044480 width=521) (actual time=59279.246..59279.264 rows=1 loops=1)" " Join Filter: (t6.kind_id = t9.id)" " -> Merge Left Join (cost=1417359.22..1429787.34 rows=1044480 width=507) (actual time=59279.222..59279.224 rows=1 loops=1)" " Merge Cond: (t6.id = t8.movie_id)" " -> Merge Left Join (cost=1405731.84..1414378.65 rows=1044480 width=491) (actual time=59121.773..59121.775 rows=1 loops=1)" " Merge Cond: (t6.id = t7.movie_id)" " -> Sort (cost=1346206.04..1348817.24 rows=1044480 width=416) (actual time=58095.230..58095.231 rows=1 loops=1)" " Sort Key: t6.id" " Sort Method: quicksort Memory: 17kB" " -> Hash Left Join (cost=172406.29..456387.53 rows=1044480 width=416) (actual time=57969.371..58095.208 rows=1 loops=1)" " Hash Cond: (t2.movie_id = t6.id)" " -> Hash Left Join (cost=104700.38..256885.82 rows=1044480 width=358) (actual time=49981.493..50006.303 rows=1 loops=1)" " Hash Cond: (t2.role_id = t5.id)" " -> Hash Left Join (cost=104699.11..242522.95 rows=1044480 width=343) (actual time=49981.441..50006.250 rows=1 loops=1)" " Hash Cond: (t2.person_role_id = t4.id)" " -> Hash Left Join (cost=464.96..12283.95 rows=1044480 width=269) (actual time=0.071..0.087 rows=1 loops=1)" " Hash Cond: (n1.id = t3.person_id)" " -> Nested Loop Left Join (cost=0.00..49.39 rows=7680 width=160) (actual time=0.051..0.066 rows=1 loops=1)" " -> Nested Loop Left Join (cost=0.00..17.04 rows=3 width=119) (actual time=0.038..0.041 rows=1 loops=1)" " -> Index Scan using name_pkey on name n1 (cost=0.00..8.68 rows=1 width=39) (actual time=0.022..0.024 rows=1 loops=1)" " Index Cond: (id = 2003)" " -> Index Scan using aka_name_idx_person on aka_name (cost=0.00..8.34 rows=1 width=80) (actual time=0.010..0.010 rows=0 loops=1)" " Index Cond: ((aka_name.person_id = 2003) AND (n1.id = aka_name.person_id))" " -> Index Scan using cast_info_idx_pid on cast_info t2 (cost=0.00..10.77 rows=1 width=41) (actual time=0.011..0.020 rows=1 loops=1)" " Index Cond: ((t2.person_id = 2003) AND (n1.id = t2.person_id))" " -> Hash (cost=463.26..463.26 rows=136 width=109) (actual time=0.010..0.010 rows=0 loops=1)" " -> Index Scan using person_info_idx_pid on person_info t3 (cost=0.00..463.26 rows=136 width=109) (actual time=0.009..0.009 rows=0 loops=1)" " Index Cond: (person_id = 2003)" " -> Hash (cost=42697.62..42697.62 rows=2442362 width=74) (actual time=49305.872..49305.872 rows=2442362 loops=1)" " -> Seq Scan on char_name t4 (cost=0.00..42697.62 rows=2442362 width=74) (actual time=14.066..22775.087 rows=2442362 loops=1)" " -> Hash (cost=1.12..1.12 rows=12 width=15) (actual time=0.024..0.024 rows=12 loops=1)" " -> Seq Scan on role_type t5 (cost=0.00..1.12 rows=12 width=15) (actual time=0.012..0.014 rows=12 loops=1)" " -> Hash (cost=31134.07..31134.07 rows=1573507 width=58) (actual time=7841.225..7841.225 rows=1573507 loops=1)" " -> Seq Scan on title t6 (cost=0.00..31134.07 rows=1573507 width=58) (actual time=21.507..2799.443 rows=1573507 loops=1)" " -> Materialize (cost=59525.80..63203.88 rows=294246 width=75) (actual time=812.376..984.958 rows=192075 loops=1)" " -> Sort (cost=59525.80..60261.42 rows=294246 width=75) (actual time=812.363..922.452 rows=192075 loops=1)" " Sort Key: t7.movie_id" " Sort Method: external merge Disk: 24880kB" " -> Seq Scan on aka_title t7 (cost=0.00..6646.46 rows=294246 width=75) (actual time=24.652..164.822 rows=294246 loops=1)" " -> Materialize (cost=11627.38..12884.43 rows=100564 width=16) (actual time=123.819..149.086 rows=41907 loops=1)" " -> Sort (cost=11627.38..11878.79 rows=100564 width=16) (actual time=123.807..138.530 rows=41907 loops=1)" " Sort Key: t8.movie_id" " Sort Method: external merge Disk: 3136kB" " -> Seq Scan on complete_cast t8 (cost=0.00..1549.64 rows=100564 width=16) (actual time=0.013..10.744 rows=100564 loops=1)" " -> Materialize (cost=1.08..1.15 rows=7 width=14) (actual time=0.016..0.029 rows=7 loops=1)" " -> Seq Scan on kind_type t9 (cost=0.00..1.07 rows=7 width=14) (actual time=0.011..0.013 rows=7 loops=1)" " -> Materialize (cost=412704.52..437969.09 rows=2021166 width=40) (actual time=3420.356..4278.545 rows=1028995 loops=1)" " -> Sort (cost=412704.52..417757.43 rows=2021166 width=40) (actual time=3420.349..3953.483 rows=1028995 loops=1)" " Sort Key: t10.movie_id" " Sort Method: external merge Disk: 90960kB" " -> Seq Scan on movie_companies t10 (cost=0.00..35214.66 rows=2021166 width=40) (actual time=13.271..566.893 rows=2021166 loops=1)" " -> Materialize (cost=3144407.19..3269057.42 rows=9972019 width=76) (actual time=65485.672..70083.219 rows=5039009 loops=1)" " -> Sort (cost=3144407.19..3169337.23 rows=9972019 width=76) (actual time=65485.667..68385.550 rows=5038999 loops=1)" " Sort Key: t11.movie_id" " Sort Method: external merge Disk: 735512kB" " -> Seq Scan on movie_info t11 (cost=0.00..212815.19 rows=9972019 width=76) (actual time=15.750..15715.608 rows=9972019 loops=1)" " -> Materialize (cost=207925.01..219867.92 rows=955433 width=50) (actual time=1483.989..1785.636 rows=429401 loops=1)" " -> Sort (cost=207925.01..210313.59 rows=955433 width=50) (actual time=1483.983..1654.165 rows=429401 loops=1)" " Sort Key: t19.movie_id" " Sort Method: external merge Disk: 31720kB" " -> Seq Scan on movie_info_idx t19 (cost=0.00..15047.33 rows=955433 width=50) (actual time=7.284..221.597 rows=955433 loops=1)" " -> Materialize (cost=501605.39..537645.64 rows=2883220 width=12) (actual time=5823.040..6868.242 rows=1597396 loops=1)" " -> Sort (cost=501605.39..508813.44 rows=2883220 width=12) (actual time=5823.026..6477.517 rows=1597396 loops=1)" " Sort Key: t12.movie_id" " Sort Method: external merge Disk: 78888kB" " -> Seq Scan on movie_keyword t12 (cost=0.00..44417.20 rows=2883220 width=12) (actual time=11.672..839.498 rows=2883220 loops=1)" " -> Materialize (cost=141143.93..152995.81 rows=948150 width=16) (actual time=1916.356..2253.004 rows=478358 loops=1)" " -> Sort (cost=141143.93..143514.31 rows=948150 width=16) (actual time=1916.344..2125.698 rows=478358 loops=1)" " Sort Key: t13.linked_movie_id" " Sort Method: external merge Disk: 29632kB" " -> Seq Scan on movie_link t13 (cost=0.00..14607.50 rows=948150 width=16) (actual time=27.610..297.962 rows=948150 loops=1)" " -> Hash (cost=1.18..1.18 rows=18 width=16) (actual time=0.020..0.020 rows=18 loops=1)" " -> Seq Scan on link_type t14 (cost=0.00..1.18 rows=18 width=16) (actual time=0.010..0.012 rows=18 loops=1)" " -> Hash (cost=1537.10..1537.10 rows=91010 width=24) (actual time=54.055..54.055 rows=91010 loops=1)" " -> Seq Scan on keyword t15 (cost=0.00..1537.10 rows=91010 width=24) (actual time=0.006..14.703 rows=91010 loops=1)" " -> Hash (cost=4585.61..4585.61 rows=245461 width=42) (actual time=445.269..445.269 rows=245461 loops=1)" " -> Seq Scan on company_name t16 (cost=0.00..4585.61 rows=245461 width=42) (actual time=12.037..309.961 rows=245461 loops=1)" " -> Hash (cost=1.04..1.04 rows=4 width=25) (actual time=0.013..0.013 rows=4 loops=1)" " -> Seq Scan on company_type t17 (cost=0.00..1.04 rows=4 width=25) (actual time=0.009..0.010 rows=4 loops=1)" " -> Hash (cost=1.04..1.04 rows=4 width=13) (actual time=0.006..0.006 rows=4 loops=1)" " -> Seq Scan on comp_cast_type t18 (cost=0.00..1.04 rows=4 width=13) (actual time=0.002..0.003 rows=4 loops=1)" "Total runtime: 147055.016 ms" Is there anyway to force the name.id = 2003 before it tries to join all the tables together? As you can see, the end result is 4 tuples but it seems like it should be a fast join by using the available index after it limited it down with the name clause, although very complex.

  Read the article

< Previous Page | 1 2 3