Search Results

Search found 26977 results on 1080 pages for 'input device'.

Page 644/1080 | < Previous Page | 640 641 642 643 644 645 646 647 648 649 650 651  | Next Page >

  • Calculating multiple column average in SQLite3

    - by Benjamin Oakes
    I need to average some values in a row-wise fashion, rather than a column-wise fashion. (If I were doing a column-wise average, I could just use avg()). My specific application of this requires me ignore NULLs in averaging. It's pretty straightforward logic, but seems awfully difficult to do in SQL. Is there an elegant way of doing my calculation? I'm using SQLite3, for what it's worth. Details If you need more details, here's an illustration: I have a a table with a survey: | q1 | q2 | q3 | ... | q144 | |----|-------|-------|-----|------| | 1 | 3 | 7 | ... | 2 | | 4 | 2 | NULL | ... | 1 | | 5 | NULL | 2 | ... | 3 | (Those are just some example values and simple column names. The valid values are 1 through 7 and NULL.) I need to calculate some averages like so: q7 + q33 + q38 + q40 + ... + q119 / 11 as domain_score_1 q10 + q11 + q34 + q35 + ... + q140 / 13 as domain_score_2 ... q2 + q5 + q13 + q25 + ... + q122 / 12 as domain_score_14 ...but i need to pull out the nulls and average based on the non-nulls. So, for domain_score_1 (which has 11 items), I would need to do: Input: 3, 5, NULL, 7, 2, NULL, 3, 1, 5, NULL, 1 (3 + 5 + 7 + 2 + 3 + 1 + 5 + 1) / (11 - 3) 27 / 8 3.375 A simple algorithm I'm considering is: Input: 3, 5, NULL, 7, 2, NULL, 3, 1, 5, NULL, 1 Coalesce each value to 0 if NULL: 3, 5, 0, 7, 2, 0, 3, 1, 5, 0, 1 Sum: 27 Get the number of non-zeros by converting values 0 to 1 and sum: 3, 5, 0, 7, 2, 0, 3, 1, 5, 0, 1 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1 8 Divide those two numbers 27 / 8 3.375 But that seems like a lot more programming than this should take. Is there an elegant way of doing this that I'm not aware of? Update: Unless I'm misunderstanding something, avg() won't work for this. Example of what I would want to do: select avg(q7, q33, q38, ..., q119) from survey; Output: SQL error near line 3: wrong number of arguments to function avg()

    Read the article

  • Something is making my page perform an Ajax call multiple times... [read: I've never been more frust

    - by Jack Webb-Heller
    NOTE: This is a long question. I've explained all the 'basics' at the top and then there's some further (optional) information for if you need it. Hi folks Basically last night this started happening at about 9PM whilst I was trying to restructure my code to make it a bit nicer for the designer to add a few bits to. I tried to fix it until 2AM at which point I gave up. Came back to it this morning, still baffled. I'll be honest with you, I'm a pretty bad Javascript developer. Since starting this project Javascript has been completely new to me and I've just learn as I went along. So please forgive me if my code structure is really bad (perhaps give a couple of pointers on how to improve it?). So, to the problem: to reproduce it, visit http://furnace.howcode.com (it's far from complete). This problem is a little confusing but I'd really appreciate the help. So in the second column you'll see three tabs The 'Newest' tab is selected by default. Scroll to the bottom, and 3 further results should be dynamically fetched via Ajax. Now click on the 'Top Rated' tab. You'll see all the results, but ordered by rating Scroll to the bottom of 'Top Rated'. You'll see SIX results returned. This is where it goes wrong. Only a further three should be returned (there are 18 entries in total). If you're observant you'll notice two 'blocks' of 3 returned. The first 'block' is the second page of results from the 'Newest' tab. The second block is what I just want returned. Did that make any sense? Never mind! So basically I checked this out in Firebug. What happens is, from a 'Clean' page (first load, nothing done) it calls ONE POST request to http://furnace.howcode.com/code/loadmore . But every time you load a new one of the tabs, it makes an ADDITIONAL POST request each time where there should normally only be ONE. So, can you help me? I'd really appreciate it! At this point you could start independent investigation or read on for a little further (optional) information. Thanks! Jack Further Info (may be irrelevant but here for reference): It's almost like there's some Javascript code or something being left behind that duplicates it each time. I thought it might be this code that I use to detect when the browser is scrolled to the bottom: var col = $('#col2'); col.scroll(function(){ if (col.outerHeight() == (col.get(0).scrollHeight - col.scrollTop())) loadMore(1); }); So what I thought was that code was left behind, and so every time you scroll #col2 (which contains different data for each tab) it detected that and added it for #newest as well. So, I made each tab click give #col2 a dynamic class - either .newestcol, .featuredcol, or .topratedcol. And then I changed the var col=$('.newestcol');dynamically so it would only detect it individually for each tab (makin' any sense?!). But hey, that didn't do anything. Another useful tidbit: here's the PHP for http://furnace.howcode.com/code/loadmore: $kind = $this->input->post('kind'); if ($kind == 1){ // kind is 1 - newest $start = $this->input->post('currentpage'); $data['query'] = "SELECT code.id AS codeid, code.title AS codetitle, code.summary AS codesummary, code.author AS codeauthor, code.rating AS rating, code.date, code_tags.*, tags.*, users.firstname AS authorname, users.id AS authorid, GROUP_CONCAT(tags.tag SEPARATOR ', ') AS taggroup FROM code, code_tags, tags, users WHERE users.id = code.author AND code_tags.code_id = code.id AND tags.id = code_tags.tag_id GROUP BY code_id ORDER BY date DESC LIMIT $start, 15 "; $this->load->view('code/ajaxlist',$data); } elseif ($kind == 2) { // kind is 2 - featured So my jQuery code sends a variable 'kind'. If it's 1, it runs the query for Newest, etc. etc. The PHP code for furnace.howcode.com/code/ajaxlist is: <?php // Our query base // SELECT * FROM code ORDER BY date DESC $query = $this->db->query($query); foreach($query->result() as $row) { ?> <script type="text/javascript"> $('#title-<?php echo $row->codeid;?>').click(function() { var form_data = { id: <?php echo $row->codeid; ?> }; $('#col3').fadeOut('slow', function() { $.ajax({ url: "<?php echo site_url('code/viewajax');?>", type: 'POST', data: form_data, success: function(msg) { $('#col3').html(msg); $('#col3').fadeIn('fast'); } }); }); }); </script> <div class="result"> <div class="resulttext"> <div id="title-<?php echo $row->codeid; ?>" class="title"> <?php echo anchor('#',$row->codetitle); ?> </div> <div class="summary"> <?php echo $row->codesummary; ?> </div> <!-- Now insert the 5-star rating system --> <?php include($_SERVER['DOCUMENT_ROOT']."/fivestars/5star.php");?> <div class="bottom"> <div class="author"> Submitted by <?php echo anchor('auth/profile/'.$row->authorid,''.$row->authorname);?> </div> <?php // Now we need to take the GROUP_CONCATted tags and split them using the magic of PHP into seperate tags $tagarray = explode(", ", $row->taggroup); foreach ($tagarray as $tag) { ?> <div class="tagbutton" href="#"> <span><?php echo $tag; ?></span> </div> <?php } ?> </div> </div> </div> <?php } echo "&nbsp;";?> <script type="text/javascript"> var newpage = <?php echo $this->input->post('currentpage') + 15;?>; </script> So that's everything in PHP. The rest you should be able to view with Firebug or by viewing the Source code. I've put all the Tab/clicking/Ajaxloading bits in the tags at the very bottom. There's a comment before it all kicks off. Thanks so much for your help!

    Read the article

  • how to set tab order in jquery

    - by Martin Ongtangco
    Hello, I'm using Telerik controls, specifically the numerical textbox where you can set a up-down arrow to increment/decrement values in a textbox. I am required to set the tab order to move to the next field but since there's a button on the up-down arrow, the browser will go through those buttons first then move to the next textbox field. How do you set the jquery to detect the next visible textbox/dropdown/etc input field and move to that on pressing the tab button instead of running through the buttons near it?

    Read the article

  • PHP contact form overwrite fields issue repeating value

    - by judi
    H I'm using php contact form from http://phpfmg.sourceforge.net/home.php. I thought I'd add an onfocus effect so when i click in the fields the value dissappears automatically. But when I submit say if haven't filled in my requried fields I get this the values appearing again like <input type="text" class="text_box" onfocus="if(this.value=='Telephone')this.value='';" value="TelephoneTelephone" id="field_5" name="field_5">

    Read the article

  • Is there a W3C valid way to disable autocomplete in a HTML form?

    - by matt b
    When using the xhtml1-transitional.dtd doctype, collecting a credit card number with the following HTML <input type="text" id="cardNumber" name="cardNumber" autocomplete='off'/> will flag a warning on the W3C validator: there is no attribute "autocomplete". Is there a W3C / standards way to disable browser auto-complete on sensitive fields in a form?

    Read the article

  • Javascript OLE Word

    - by Martijn
    I want to show a MS Word environment in an Iframe without all the toobars. The document that is being showed contains input fields. After these fields are filled in, the document must be printed. I have created the print button and want the (filled in) document printed when this button is clicked. I hope you understand want I want and hope you can help out.

    Read the article

  • Biztalk Flat File Schema - how to accept a LF or CRLF as the line delimiter

    - by FullOfQuestions
    Hi, Our client sends us a flat file as input, which we then take and convert to an XML file before sending to the destination system. The flat file consists of multiple lines, each line is delimited by LF or CRLF. How do I create a Flat File Schema so that Biztalk can interpret each line of data regardless of whether the line was delimited by LF (0x0A) or CRLF (0x0D 0x0A)? Thank you in advance, M

    Read the article

  • Multiple forms with shared fields

    - by SMiX
    How to make multiple forms with shared fields without using javascript? <input type=text name=username /> <form action="/users"> ... some fields ... </form> <form action="/admins"> ... some another fields ... </form>

    Read the article

  • JQuery overriding the themeroller style

    - by Paul Connolly
    Hi, In my accordian control I want to override the header style to show a red background instead of the default theme colour if ever the user control (e.g user's name and address input) in that particular pane returns a validation boolean of false. I'm ok with how to use .Toggle to change the class but can't figure out how to grab the themeroller class in the first place. How would I do this? Thanks Paul

    Read the article

  • onClientClick event

    - by picnic4u
    when i used onClientClick event for calling a javascript function in .aspx file. but it's not working at all.how can i get alert for input of data within "<" in textbox. pls help me

    Read the article

  • str is not callable error in python .

    - by mekasperasky
    import sys import md5 from TOSSIM import * from RadioCountMsg import * t = Tossim([]) #The Tossim object is defined here m = t.mac()#The mac layer is defined here , in which the communication takes place r = t.radio()#The radio communication link object is defined here , as the communication needs Rf frequency to transfer t.addChannel("RadioCountToLedsC", sys.stdout)# The various channels through which communication will take place t.addChannel("LedsC", sys.stdout) #The no of nodes that would be required in the simulation has to be entered here print("enter the no of nodes you want ") n=input() for i in range(0, n): m = t.getNode(i) m.bootAtTime((31 + t.ticksPerSecond() / 10) * i + 1) #The booting time is defined so that the time at which the node would be booted is given f = open("topo.txt", "r") #The topography is defined in topo.txt so that the RF frequencies of the transmission between nodes are are set lines = f.readlines() for line in lines: s = line.split() if (len(s) > 0): if (s[0] == "gain"): r.add(int(s[1]), int(s[2]), float(s[3])) #The topogrography is added to the radio object noise = open("meyer-heavy.txt", "r") #The noise model is defined for the nodes lines = noise.readlines() for line in lines: str = line.strip() if (str != ""): val = int(str) for i in range(0, 4): t.getNode(i).addNoiseTraceReading(val) for i in range (0, n): t.getNode(i).createNoiseModel() #The noise model is created for each node for i in range(0,n): t.runNextEvent() fk=open("key.txt","w") for i in range(0,n): if i ==0 : key=raw_input() fk.write(key) ak=key key=md5.new() key.update(str(ak)) ak=key.digest() fk.write(ak) fk.close() fk=open("key.txt","w") plaint=open("pt.txt") for i in range(0,n): msg = RadioCountMsg() msg.set_counter(7) pkt = t.newPacket()#A packet is defined according to a certain format print("enter message to be transported") ms=raw_input()#The message to be transported is taken as input #The RC5 encryption has to be done here plaint.write(ms) pkt.setData(msg.data) pkt.setType(msg.get_amType()) pkt.setDestination(i+1)#The destination to which the packet will be sent is set print "Delivering " + " to" ,i+1 pkt.deliver(i+1, t.time() + 3) fk.close() print "the key to be displayed" ki=raw_input() fk=open("key.txt") for i in range(0,n): if i==ki: ms=fk.readline() for i in range(0,n): msg=RadioCountMsg() msg.set_counter(7) pkt=t.newPacket() msg.data=ms pkt.setData(msg.data) pkt.setType(msg.get_amType()) pkt.setDestination(i+1) pkt.deliver(i+1,t.time()+3) #The key has to be broadcasted here so that the decryption can take place for i in range(0, n): t.runNextEvent(); this code gives me error here key.update(str(ak)) . when i run a similar code on the python terminal there is no such error but this code pops up an error . why so?

    Read the article

  • Signal Handling in C

    - by Dave
    How can I implement signal Handling for Ctrl-C and Ctrl-D in C....So If Ctrl-C is pressed then the program will ignore and try to get the input from the user again...If Ctrl-D is pressed then the program will terminate... My program follows: int main(){ char msg[400]; while(1){ printf("Enter: "); fgets(msg,400,stdin); printf("%s\n",msg); } } Thanks, Dave

    Read the article

  • help with making a password checker in java

    - by Cheesegraterr
    Hello, I am trying to make a program in Java that checks for three specific inputs. It has to be 1. At least 7 characters. 2. Contain both upper and lower case alphabetic characters. 3. Contain at least 1 digit. So far I have been able to make it check if there is 7 characters, but I am having trouble with the last two. What should I put in my loop as an if statement to check for digits and make it upper and lower case. Any help would be greatly appreciated. Here is what I have so far. import java.awt.*; import java.io.*; import java.util.StringTokenizer; public class passCheck { private static String getStrSys () { String myInput = null; //Store the String that is read in from the command line BufferedReader mySystem; //Buffer to store the input mySystem = new BufferedReader (new InputStreamReader (System.in)); //creates a connection to system input try { myInput = mySystem.readLine (); //reads in data from the console myInput = myInput.trim (); } catch (IOException e) //check { System.out.println ("IOException: " + e); return ""; } return myInput; //return the integer to the main program } //**************************************** //main instructions go here //**************************************** static public void main (String[] args) { String pass; //the words the user inputs String temp = ""; //holds temp info int stringLength; //length of string boolean goodPass = false; System.out.print ("Please enter a password: "); //ask for words pass = getStrSys (); //get words from system temp = pass.toLowerCase (); stringLength = pass.length (); //find length of eveyrthing while (goodPass == false) { if (stringLength < 7) { System.out.println ("Your password must consist of at least 7 characters"); System.out.print ("Please enter a password: "); //ask for words pass = getStrSys (); stringLength = pass.length (); goodPass = false; } else if (something to check for digits) { } }

    Read the article

  • Silverlight changes the io.Stream to byte[]

    - by Sai
    I have created a WCF service for uploading images , which accepts System.IO.Stream as input parameter and am using streaming. When I added the service reference in Silverlight project then it automatically changed the parameter of my WCF method from System.IO.Stream to byte[]. Can anyone suggest if there is a way around this so that I can get System.IO.Stream type rather than byte[]. Thanks in advance

    Read the article

  • how to use two forms and sumit once

    - by Mac Taylor
    hey guys is it possible to have two forms with two submit buttons but when i click on the button then it saves both forms input fields im concerning to solve this in php /mysql i tried my own way : if ((isset($_POST["form-1"])) && (isset($_POST["form-2"])) { //SQL Insertion } thanks in advance

    Read the article

  • Reset element color to default stylesheet color (Jquery, Javascript)

    - by leaf dev
    I need to be able to reset an input field back to its original color after it has been possibly changed via javascript to a different value. The problem is I do not want to hard code the value obviously in case the stylesheet changes. I would like to use the default color used on the page. Is resetting the color like this fine, or is there a better way to do this? $('#theinput').css('color', '');

    Read the article

  • Implementing a robust async stream reader

    - by Jon
    I recently provided an answer to this question: C# - Realtime console output redirection. As often happens, explaining stuff (here "stuff" was how I tackled a similar problem) leads you to greater understanding and/or, as is the case here, "oops" moments. I realized that my solution, as implemented, has a bug. The bug has little practical importance, but it has an extremely large importance to me as a developer: I can't rest easy knowing that my code has the potential to blow up. Squashing the bug is the purpose of this question. I apologize for the long intro, so let's get dirty. I wanted to build a class that allows me to receive input from a Stream in an event-based manner. The stream, in my scenario, is guaranteed to be a FileStream and there is also an associated StreamReader already present to leverage. The public interface of the class is this: public class MyStreamManager { public event EventHandler<ConsoleOutputReadEventArgs> StandardOutputRead; public void StartSendingEvents(); public void StopSendingEvents(); } Obviously this specific scenario has to do with a console's standard output, but that is a detail and does not play an important role. StartSendingEvents and StopSendingEvents do what they advertise; for the purposes of this discussion, we can assume that events are always being sent without loss of generality. The class uses these two fields internally: protected readonly StringBuilder inputAccumulator = new StringBuilder(); protected readonly byte[] buffer = new byte[256]; The functionality of the class is implemented in the methods below. To get the ball rolling: public void StartSendingEvents(); { this.stopAutomation = false; this.BeginReadAsync(); } To read data out of the Stream without blocking, and also without requiring a carriage return char, BeginRead is called: protected void BeginReadAsync() { if (!this.stopAutomation) { this.StandardOutput.BaseStream.BeginRead( this.buffer, 0, this.buffer.Length, this.ReadHappened, null); } } The challenging part: BeginRead requires using a buffer. This means that when reading from the stream, it is possible that the bytes available to read ("incoming chunk") are larger than the buffer. Since we are only handing off data from the stream to a consumer, and that consumer may well have inside knowledge about the size and/or format of these chunks, I want to call event subscribers exactly once for each chunk. Otherwise the abstraction breaks down and the subscribers have to buffer the incoming data and reconstruct the chunks themselves using said knowledge. This is much less convenient to the calling code, and detracts from the usefulness of my class. To this end, if the buffer is full after EndRead, we don't send its contents to subscribers immediately but instead append them to a StringBuilder. The contents of the StringBuilder are only sent back whenever there is no more to read from the stream (thus preserving the chunks). private void ReadHappened(IAsyncResult asyncResult) { var bytesRead = this.StandardOutput.BaseStream.EndRead(asyncResult); if (bytesRead == 0) { this.OnAutomationStopped(); return; } var input = this.StandardOutput.CurrentEncoding.GetString( this.buffer, 0, bytesRead); this.inputAccumulator.Append(input); if (bytesRead < this.buffer.Length) { this.OnInputRead(); // only send back if we 're sure we got it all } this.BeginReadAsync(); // continue "looping" with BeginRead } After any read which is not enough to fill the buffer, all accumulated data is sent to the subscribers: private void OnInputRead() { var handler = this.StandardOutputRead; if (handler == null) { return; } handler(this, new ConsoleOutputReadEventArgs(this.inputAccumulator.ToString())); this.inputAccumulator.Clear(); } (I know that as long as there are no subscribers the data gets accumulated forever. This is a deliberate decision). The good This scheme works almost perfectly: Async functionality without spawning any threads Very convenient to the calling code (just subscribe to an event) Maintains the "chunkiness" of the data; this allows the calling code to use inside knowledge of the data without doing any extra work Is almost agnostic to the buffer size (it will work correctly with any size buffer irrespective of the data being read) The bad That last almost is a very big one. Consider what happens when there is an incoming chunk with length exactly equal to the size of the buffer. The chunk will be read and buffered, but the event will not be triggered. This will be followed up by a BeginRead that expects to find more data belonging to the current chunk in order to send it back all in one piece, but... there will be no more data in the stream. In fact, as long as data is put into the stream in chunks with length exactly equal to the buffer size, the data will be buffered and the event will never be triggered. This scenario may be highly unlikely to occur in practice, especially since we can pick any number for the buffer size, but the problem is there. Solution? Unfortunately, after checking the available methods on FileStream and StreamReader, I can't find anything which lets me peek into the stream while also allowing async methods to be used on it. One "solution" would be to have a thread wait on a ManualResetEvent after the "buffer filled" condition is detected. If the event is not signaled (by the async callback) in a small amount of time, then more data from the stream will not be forthcoming and the data accumulated so far should be sent to subscribers. However, this introduces the need for another thread, requires thread synchronization, and is plain inelegant. Specifying a timeout for BeginRead would also suffice (call back into my code every now and then so I can check if there's data to be sent back; most of the time there will not be anything to do, so I expect the performance hit to be negligible). But it looks like timeouts are not supported in FileStream. Since I imagine that async calls with timeouts are an option in bare Win32, another approach might be to PInvoke the hell out of the problem. But this is also undesirable as it will introduce complexity and simply be a pain to code. Is there an elegant way to get around the problem? Thanks for being patient enough to read all of this.

    Read the article

  • Codeigniter initializing multiple times per page load

    - by Clayton
    I'm using Codeigniter for my application and have something wrong with my configuration. When I load a page, the framework initializes several times (see logs below). I have built other applications with Codeigniter and have never seen this behavior before. Log output: DEBUG - 2010-03-27 14:50:32 --> Config Class Initialized DEBUG - 2010-03-27 14:50:32 --> Hooks Class Initialized DEBUG - 2010-03-27 14:50:32 --> URI Class Initialized DEBUG - 2010-03-27 14:50:32 --> Router Class Initialized DEBUG - 2010-03-27 14:50:32 --> Output Class Initialized DEBUG - 2010-03-27 14:50:32 --> Input Class Initialized DEBUG - 2010-03-27 14:50:32 --> XSS Filtering completed DEBUG - 2010-03-27 14:50:32 --> XSS Filtering completed DEBUG - 2010-03-27 14:50:32 --> XSS Filtering completed DEBUG - 2010-03-27 14:50:32 --> XSS Filtering completed DEBUG - 2010-03-27 14:50:32 --> Global POST and COOKIE data sanitized DEBUG - 2010-03-27 14:50:32 --> Language Class Initialized DEBUG - 2010-03-27 14:50:32 --> Loader Class Initialized DEBUG - 2010-03-27 14:50:32 --> Config file loaded: config/redux_auth.php DEBUG - 2010-03-27 14:50:32 --> Config file loaded: config/email.php DEBUG - 2010-03-27 14:50:32 --> Helper loaded: url_helper DEBUG - 2010-03-27 14:50:32 --> Helper loaded: form_helper DEBUG - 2010-03-27 14:50:32 --> Helper loaded: html_helper DEBUG - 2010-03-27 14:50:32 --> Database Driver Class Initialized DEBUG - 2010-03-27 14:50:32 --> Session Class Initialized DEBUG - 2010-03-27 14:50:32 --> Helper loaded: string_helper DEBUG - 2010-03-27 14:50:32 --> Helper loaded: file_helper DEBUG - 2010-03-27 14:50:32 --> Session routines successfully run DEBUG - 2010-03-27 14:50:32 --> Form Validation Class Initialized DEBUG - 2010-03-27 14:50:32 --> Model Class Initialized DEBUG - 2010-03-27 14:50:32 --> Controller Class Initialized DEBUG - 2010-03-27 14:50:32 --> Language file loaded: language/english/form_validation_lang.php DEBUG - 2010-03-27 14:50:32 --> XSS Filtering completed DEBUG - 2010-03-27 14:50:32 --> XSS Filtering completed DEBUG - 2010-03-27 14:50:32 --> Config Class Initialized DEBUG - 2010-03-27 14:50:32 --> Hooks Class Initialized DEBUG - 2010-03-27 14:50:32 --> URI Class Initialized DEBUG - 2010-03-27 14:50:32 --> Router Class Initialized DEBUG - 2010-03-27 14:50:32 --> Output Class Initialized DEBUG - 2010-03-27 14:50:32 --> Input Class Initialized DEBUG - 2010-03-27 14:50:32 --> XSS Filtering completed DEBUG - 2010-03-27 14:50:32 --> Global POST and COOKIE data sanitized DEBUG - 2010-03-27 14:50:32 --> Language Class Initialized DEBUG - 2010-03-27 14:50:32 --> Loader Class Initialized ... This repeats three more times

    Read the article

  • Most efficient method to query a Young Tableau

    - by Matthieu M.
    A Young Tableau is a 2D matrix A of dimensions M*N such that: i,j in [0,M)x[0,N): for each p in (i,M), A[i,j] <= A[p,j] for each q in (j,N), A[i,j] <= A[i,q] That is, it's sorted row-wise and column-wise. Since it may contain less than M*N numbers, the bottom-right values might be represented either as missing or using (in algorithm theory) infinity to denote their absence. Now the (elementary) question: how to check if a given number is contained in the Young Tableau ? Well, it's trivial to produce an algorithm in O(M*N) time of course, but what's interesting is that it is very easy to provide an algorithm in O(M+N) time: Bottom-Left search: Let x be the number we look for, initialize i,j as M-1, 0 (bottom left corner) If x == A[i,j], return true If x < A[i,j], then if i is 0, return false else decrement i and go to 2. Else, if j is N-1, return false else increment j This algorithm does not make more than M+N moves. The correctness is left as an exercise. It is possible though to obtain a better asymptotic runtime. Pivot Search: Let x be the number we look for, initialize i,j as floor(M/2), floor(N/2) If x == A[i,j], return true If x < A[i,j], search (recursively) in A[0:i-1, 0:j-1], A[i:M-1, 0:j-1] and A[0:i-1, j:N-1] Else search (recursively) in A[i+1:M-1, 0:j], A[i+1:M-1, j+1:N-1] and A[0:i, j+1:N-1] This algorithm proceed by discarding one of the 4 quadrants at each iteration and running recursively on the 3 left (divide and conquer), the master theorem yields a complexity of O((N+M)**(log 3 / log 4)) which is better asymptotically. However, this is only a big-O estimation... So, here are the questions: Do you know (or can think of) an algorithm with a better asymptotical runtime ? Like introsort prove, sometimes it's worth switching algorithms depending on the input size or input topology... do you think it would be possible here ? For 2., I am notably thinking that for small size inputs, the bottom-left search should be faster because of its O(1) space requirement / lower constant term.

    Read the article

< Previous Page | 640 641 642 643 644 645 646 647 648 649 650 651  | Next Page >