Provided `itemgetter(0)` is `O(1)` when used with `data`, the sort is `O(n log n)` both on average and in the worst case.

For more information on the sorting method used in Python, see [Wikipedia][1].


  [1]: http://en.wikipedia.org/wiki/Timsort

sorted is like sort except that the first builds a new sorted list from an iterable while sort do sort in place. The main difference will be space complexity.

It is the Timsort, and Timsort is a kind of adaptive sorting algorithm based on merge sort and insertion sort, then I thought it belongs to the comparison sort, and [it&#39;s said](http://en.wikipedia.org/wiki/Comparison_sort#Number_of_comparisons_required_to_sort_a_list), no comparison sort can guarantee a time complexity smaller than lg(N!) ~ N log N.

Just like in every other programming language, the sorted() has O(NlogN) Time Complexity.

My problem is: sometimes browser over-cached some resources even if i&#39;ve already modified them. But After F5, everything is fine.

I studied this case whole afternoon. Now i completely understood the point of &quot;Last-Modified&quot; or &quot;Cache-Control&quot;. And i know how to solve my **issue** (just .js?version or explicit max-age=xxxx). But the **problem** is still unsolved: how does browser handle the response header **without** &quot;Cache-Control&quot; like this:

    Content-Length: 49675
    Content-Type: text/html
    Last-Modified: Thu, 27 Dec 2012 03:03:50 GMT
    Accept-Ranges: bytes
    Etag: &quot;0af7fcbdee3cd1:972&quot;
    Server: Microsoft-IIS/6.0
    X-Powered-By: ASP.NET
    Date: Thu, 24 Jan 2013 07:46:16 GMT 

They clearly cache them when &quot;Enter in the bar&quot;

![enter image description here][1]

 


  [1]: http://i.stack.imgur.com/3hJnn.jpg

What&#39;s default value of cache-control?

How do I actually get jsfiddle to use more than 1 library? I can only seem to get it to use either jquery OR knockout but not both. Yet when I look at other peoples fiddles they dont seem to have this problem. Really annoying dont know why its so diffuclt and no searches on the internet yielded anything!!!

Thanks

How do I select more than 1 framework with jsFiddle?

I have a list of lists and I am sorting them using the following 

    data=sorted(data, key=itemgetter(0))

Was wondering what is the runtime complexity of this python function?

 

What is the complexity of the sorted() function?

I have a list of lists and I am sorting them using the following
<pre><code class="hljs language-ini">data=sorted(data, key=itemgetter(0))
</code></pre>
Was wondering what is the runtime complexity of this python function?

I came across this sample of code from a [radix sort][1]:

&lt;!-- language: lang-py --&gt;

    def getDigit(num, base, digit_num):
        # pulls the selected digit
        return (num // base ** digit_num) % base

What does the `//` do in Python?


  [1]: http://en.wikipedia.org/wiki/Radix_sort#Example_in_Python

Two forward slashes in Python

So in Java, we can do https://stackoverflow.com/questions/313893/how-to-measure-time-taken-by-a-function-to-execute

But how is it done in python? To measure the time start and end time between lines of codes?
Something that does this:

    import some_time_library
    
    starttime = some_time_library.some_module()
    code_tobe_measured() 
    endtime = some_time_library.some_module()
 
    time_taken = endtime - starttime

How to measure time taken between lines of code in python?

I have just done some image processing using the Python image library (PIL) using a post I found earlier to perform fourier transforms of images and I can&#39;t get the save function to work. The whole code works fine but it just wont save the resulting image:

    from PIL import Image
    import numpy as np
    
    i = Image.open(&quot;C:/Users/User/Desktop/mesh.bmp&quot;)
    i = i.convert(&quot;L&quot;)
    a = np.asarray(i)
    b = np.abs(np.fft.rfft2(a))
    j = Image.fromarray(b)
    j.save(&quot;C:/Users/User/Desktop/mesh_trans&quot;,&quot;.bmp&quot;)

The error I get is the following:

    save_handler = SAVE[string.upper(format)] # unknown format
        KeyError: &#39;.BMP&#39;

How can I save an image with Pythons PIL?

How can I save an image with PIL?

&gt; **Possible Duplicate:**  
&gt; [Ternary conditional operator in Python](https://stackoverflow.com/questions/394809/ternary-conditional-operator-in-python)  

&lt;!-- End of automatically inserted text --&gt;

I want to do the following in python:

    while( i &lt; someW &amp;&amp; j &lt; someX){
       int x = A[i] &gt; B[j]? A[i++]:B[j++];
       ....
    }
Clearly, when either `i` or `j` hits a limit, the code will break out of the loop. I need the values of `i` and `j` outside of the loop.

Must I really do

    x=0
    ...
    if A[i] &gt; B[j]:
      x = A[i]
      i+=1
    else:
      x = B[j]
      j+=1

Or does anyone know of a shorter way?

Besides the above, can I get Python to support something similar to

    a,b=5,7
    x = a &gt; b ? 10 : 11


Python if-else short-hand

I am working with code that throws a lot of (for me at the moment) useless warnings using the [`warnings`][1] library. Reading (/scanning) the documentation I only found a way [to disable warnings for single functions][2]. But I don&#39;t want to change so much of the code. 

Is there a flag like `python -no-warning foo.py`? 

What would you recommend?


  [1]: https://docs.python.org/3/library/warnings.html
  [2]: https://docs.python.org/3/library/warnings.html#temporarily-suppressing-warnings


How to disable Python warnings?

I made a class called `QuickRandom`, and its job is to produce random numbers quickly. It&#39;s really simple: just take the old value, multiply by a `double`, and take the decimal part.

Here is my `QuickRandom` class in its entirety:

    public class QuickRandom {
    	private double prevNum;
    	private double magicNumber;
    	
    	public QuickRandom(double seed1, double seed2) {
    		if (seed1 &gt;= 1 || seed1 &lt; 0) throw new IllegalArgumentException(&quot;Seed 1 must be &gt;= 0 and &lt; 1, not &quot; + seed1);
    		prevNum = seed1;
    		if (seed2 &lt;= 1 || seed2 &gt; 10) throw new IllegalArgumentException(&quot;Seed 2 must be &gt; 1 and &lt;= 10, not &quot; + seed2);
    		magicNumber = seed2;
    	}
    	
    	public QuickRandom() {
    		this(Math.random(), Math.random() * 10);
    	}
    	
    	public double random() {
    		return prevNum = (prevNum*magicNumber)%1;
    	}
    
    }

And here is the code I wrote to test it:

	public static void main(String[] args) {
    		QuickRandom qr = new QuickRandom();
    		
    		/*for (int i = 0; i &lt; 20; i ++) {
    			System.out.println(qr.random());
    		}*/
    		
    		//Warm up
    		for (int i = 0; i &lt; 10000000; i ++) {
    			Math.random();
    			qr.random();
    			System.nanoTime();
    		}
    		
    		long oldTime;
    		
    		oldTime = System.nanoTime();
    		for (int i = 0; i &lt; 100000000; i ++) {
    			Math.random();
    		}
    		System.out.println(System.nanoTime() - oldTime);
    		
    		oldTime = System.nanoTime();
    		for (int i = 0; i &lt; 100000000; i ++) {
    			qr.random();
    		}
    		System.out.println(System.nanoTime() - oldTime);
	}

It is a very simple algorithm that simply multiplies the previous double by a &quot;magic number&quot; double. I threw it together pretty quickly, so I could probably make it better, but strangely, it seems to be working fine.

This is sample output of the commented-out lines in the `main` method:

    0.612201846732229
    0.5823974655091941
    0.31062451498865684
    0.8324473610354004
    0.5907187526770246
    0.38650264675748947
    0.5243464344127049
    0.7812828761272188
    0.12417247811074805
    0.1322738256858378
    0.20614642573072284
    0.8797579436677381
    0.022122999476108518
    0.2017298328387873
    0.8394849894162446
    0.6548917685640614
    0.971667953190428
    0.8602096647696964
    0.8438709031160894
    0.694884972852229

Hm. Pretty random. In fact, that would work for a random number generator in a game.

Here is sample output of the non-commented out part:

    5456313909
    1427223941

Wow! It performs almost 4 times faster than `Math.random`.

I remember reading somewhere that `Math.random` used `System.nanoTime()` and tons of crazy modulus and division stuff. Is that really necessary? My algorithm performs a lot faster and it seems pretty random.

I have two questions:

- Is my algorithm &quot;good enough&quot; (for, say, a game, where **really** random numbers aren&#39;t too important)?
- Why does `Math.random` do so much when it seems just simple multiplication and cutting out the decimal will suffice?

Is this a &quot;good enough&quot; random algorithm; why isn&#39;t it used if it&#39;s faster?

I was wondering about how can one find the nth term of fibonacci sequence for a very large value of n say, 1000000. Using the grade-school recurrence equation `fib(n)=fib(n-1)+fib(n-2)`, it takes 2-3 min to find the 50th term! 

After googling, I came to know about Binet&#39;s formula but it is not appropriate for values of n&gt;79 as it is said [here][1]

Is there an algorithm to do so just like we have for finding prime numbers?


  [1]: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibFormula.html

Finding out nth fibonacci number for very large &#39;n&#39;

Are the _trie_ and _radix trie_ data structures the same thing?
 
If they aren&#39;t the same, then what is the meaning of radix trie (AKA Patricia trie)?


What is the difference between trie and radix trie data structures?

I have been asked this question in a job interview and I have been wondering about the right answer.

&gt; You have an array of numbers from 0 to n-1, one of the numbers is removed, and replaced with a number already in the array which makes a duplicate of that number. How can we detect this duplicate in time *O(n)*?

For example, an array of `4,1,2,3` would become `4,1,2,2`.

The easy solution of time *O(n&lt;sup&gt;2&lt;/sup&gt;)* is to use a nested loop to look for the duplicate of each element.

Find duplicate element in array in time O(n)

I have a program that shows you whether two words are anagrams of one another. There are a few examples that will not work properly and I would appreciate any help, although if it were not advanced that would be great, as I am a 1st year programmer. &quot;schoolmaster&quot; and &quot;theclassroom&quot; are anagrams of one another, however when I change &quot;theclassroom&quot; to &quot;theclafsroom&quot; it still says they are anagrams, what am I doing wrong?

```java
import java.util.ArrayList;
public class AnagramCheck {
    public static void main(String args[]) {
        String phrase1 = &quot;tbeclassroom&quot;;
        phrase1 = (phrase1.toLowerCase()).trim();
        char[] phrase1Arr = phrase1.toCharArray();

        String phrase2 = &quot;schoolmaster&quot;;
        phrase2 = (phrase2.toLowerCase()).trim();
        ArrayList&lt;Character&gt; phrase2ArrList = convertStringToArraylist(phrase2);

        if (phrase1.length() != phrase2.length()) {
            System.out.print(&quot;There is no anagram present.&quot;);
        } else {
            boolean isFound = true;
            for (int i = 0; i &lt; phrase1Arr.length; i++) {
                for (int j = 0; j &lt; phrase2ArrList.size(); j++) {
                    if (phrase1Arr[i] == phrase2ArrList.get(j)) {
                        System.out.print(&quot;There is a common element.\n&quot;);
                        isFound =;
                        phrase2ArrList.remove(j);
                    }
                }
                if (isFound == false) {
                    System.out.print(&quot;There are no anagrams present.&quot;);
                    return;
                }
            }
            System.out.printf(&quot;%s is an anagram of %s&quot;, phrase1, phrase2);
        }
    }

    public static ArrayList&lt;Character&gt; convertStringToArraylist(String str) {
        ArrayList&lt;Character&gt; charList = new ArrayList&lt;Character&gt;();
        for (int i = 0; i &lt; str.length(); i++) {
            charList.add(str.charAt(i));
        }
        return charList;
    }
}
```


How to check if two words are anagrams

How do I sort a list of date and/or datetime objects? The accepted answer [here][1] isn&#39;t working for me:


    from datetime import datetime,date,timedelta
    
    
    a=[date.today(), date.today() + timedelta(days=1), date.today() - timedelta(days=1)]
    print a # prints &#39;[datetime.date(2013, 1, 22), datetime.date(2013, 1, 23), datetime.date(2013, 1, 21)]&#39;
    a = a.sort()
    print a # prints &#39;None&#39;....what???


  [1]: https://stackoverflow.com/questions/9907670/how-to-sort-list-of-date-object

How do I sort a list of datetime or date objects?

I have a fixed-width-field file which I&#39;m trying to sort using the UNIX (Cygwin, in my case) sort utility.

The problem is there is a two-line header at the top of the file which is being sorted to the bottom of the file (as each header line begins with a colon).

Is there a way to tell sort either &quot;pass the first two lines across unsorted&quot; or to specify an ordering which sorts the colon lines to the top - the remaining lines are always start with a 6-digit numeric (which is actually the key I&#39;m sorting on) if that helps.

Example:

    :0:12345
    :1:6:2:3:8:4:2
    010005TSTDOG_FOOD01
    500123TSTMY_RADAR00
    222334NOTALINEOUT01
    477821USASHUTTLES21
    325611LVEANOTHERS00

should sort to:

    :0:12345
    :1:6:2:3:8:4:2
    010005TSTDOG_FOOD01
    222334NOTALINEOUT01
    325611LVEANOTHERS00
    477821USASHUTTLES21
    500123TSTMY_RADAR00


Is there a way to ignore header lines in a UNIX sort?

By switching a javascript sort function from

    myArray.sort(function (a, b) {
      return a.name.localeCompare(b.name);
    });

to

    myArray.sort(function (a, b) {
      return (a.name &lt; b.name ? -1 : (a.name &gt; b.name ? 1 : 0));
    });

I was able to cut the time to sort a ~1700 element array in Chrome from 1993 milliseconds to 5 milliseconds. Almost a 400x speedup. Unfortunately this is at the expense of correctly sorting non-english strings.

Obviously I can&#39;t have my UI blocking for 2 seconds when I try to do a sort. Is there anything I can do to avoid the horribly slow localeCompare but still maintain support for localized strings?

400x Sorting Speedup by Switching a.localeCompare(b) to (a&lt;b?-1:(a&gt;b?1:0))

I have a dataset with multi-index columns in a pandas df that I would like to sort by values in a specific column.  I have tried using sortindex and sortlevel but haven&#39;t been able get the results I am looking for.  My dataset looks like:

        Group1    Group2
        A B C     A B C
    1   1 0 3     2 5 7
    2   5 6 9     1 0 0
    3   7 0 2     0 3 5 

I want to sort all data and the index by column C in Group 1 in descending order so my results look like:

        Group1    Group2
        A B C     A B C
     2  5 6 9     1 0 0
     1  1 0 3     2 5 7
     3  7 0 2     0 3 5 


Is it possible to do this sort with the structure that my data is in, or should I be swapping Group1 to the index side?


Multi Index Sorting in Pandas

Given the following dataframe

    In [31]: rand = np.random.RandomState(1)
             df = pd.DataFrame({&#39;A&#39;: [&#39;foo&#39;, &#39;bar&#39;, &#39;baz&#39;] * 2,
                                &#39;B&#39;: rand.randn(6),
                                &#39;C&#39;: rand.rand(6) &gt; .5})

    In [32]: df
    Out[32]:      A         B      C
             0  foo  1.624345  False
             1  bar -0.611756   True
             2  baz -0.528172  False
             3  foo -1.072969   True
             4  bar  0.865408  False
             5  baz -2.301539   True 

                   

I would like to sort it in groups (`A`) by the aggregated sum of `B`, and then by the value in `C` (not aggregated). So basically get the order of the `A` groups with

    In [28]: df.groupby(&#39;A&#39;).sum().sort(&#39;B&#39;)
    Out[28]:             B  C
             A               
             baz -2.829710  1
             bar  0.253651  1
             foo  0.551377  1

And then by True/False, so that it ultimately looks like this:

    In [30]: df.ix[[5, 2, 1, 4, 3, 0]]
    Out[30]: A         B      C
        5  baz -2.301539   True
        2  baz -0.528172  False
        1  bar -0.611756   True
        4  bar  0.865408  False
        3  foo -1.072969   True
        0  foo  1.624345  False

How can this be done?                         

Content Type	Original Author	Original Content on Stackoverflow
Question	Read Q	View Question on Stackoverflow
Solution 1 - Python	NPE	View Answer on Stackoverflow
Solution 2 - Python	blackmath	View Answer on Stackoverflow
Solution 3 - Python	Lerner Zhang	View Answer on Stackoverflow
Solution 4 - Python	Fahad Nadeem	View Answer on Stackoverflow

What is the complexity of the sorted() function?

Python Problem Overview

Python Solutions

Solution 1 - Python

Solution 2 - Python

Solution 3 - Python

Solution 4 - Python

How do I select more than 1 framework with jsFiddle?

What's default value of cache-control?

Attributions