This challenge is based on [the kata](https://www.codewars.com/kata/n-smallest-elements-in-original-order) by GiacomoSorbi. Before doing this one it is advisable to complete the non-performance version first.

___

# Task

You will be given an array of random integers and a number `n`. You have to extract `n` smallest integers out of it **preserving the original order**.

# Examples

```python
performant_smallest([1, 2, 3, 4, 5], 3)     ==   [1, 2, 3]
performant_smallest([5, 4, 3, 2, 1], 3)     ==   [3, 2, 1]
performant_smallest([1, 2, 3, 4, 1], 3)     ==   [1, 2, 1]
performant_smallest([2, 1, 3, 2, 3], 3)     ==   [2, 1, 2]
```

# Notes

* There will be duplicates in the array, and they have to be returned in the order of their each separate appearence.
* This kata is an example of the "know your data" principle. Remember this while searching for the correct approach.

# Performance tests

```python
Tests: 15
Array size: 800,000
Values range: [1; 50]
Number of elements to return: 25-50% of the array
```

Difficulty: introductory

Starter code:

def performant_smallest(arr, n):
	

Solutions:
from collections import Counter
from itertools import count, islice

def performant_smallest(arr, n):
    cnts = Counter(arr)
    total = 0
    for i, c in sorted(cnts.items()):
        total += c
        if total >= n:
            break
    available = count(c + n - total, -1)
    it = (x for x in arr if x < i or (x == i and next(available) > 0))
    return list(islice(it, n))

def performant_smallest(xs, n):
    ys = sorted(xs)
    del ys[n:]
    m = ys[-1]
    km = ys.count(m)
    res = []
    for x in xs:
        if x <= m:
            if x < m:
                res.append(x)
            elif km > 0:
                res.append(x)
                km -= 1
    return res

def performant_smallest(arr, n):
    keys = sorted(list(range(len(arr))), key=arr.__getitem__)
    return [arr[i] for i in sorted(keys[:n])]


import numpy as np
def performant_smallest(a, n):
    l = len(a)
    arr = np.array([v + (i / l) for i, v in enumerate(a)])
    ag = np.argpartition(arr, n - 1)
    args = np.sort(ag[:n])
    return [a[x] for x in args]

def performant_smallest(lst, n):
    c = [0]*201     #Our counter.
    for itm in lst:     c[itm+100] += 1     #Map each number to num+100.
    res, sm = [0]*n, 0
    for k in range(201):    #Iterate through the numbers in our counter.
        sm += c[k]
        if sm >= n:
            c[k] += n - sm  #The sum of `c[:k+1]` should be equal to `n`, and this would give us the count of the `n` smallest elements.
            break
    sm = 0
    for itm in lst:     #Iterate through the list to present the elements in their appearance order in the list.
        v = itm+100     #The mapping between the list item and its index in our counter.
        if v <= k and c[v] > 0:     #The item is one of the `n` smallest items.
            res[sm] = itm   #Place it in its position in the result list.
            sm += 1
            c[v] -= 1
        if sm == n: break
    return res

def performant_smallest(arr, n):
    c = [0]*51
    o = [0]*n
    #Count each number 1-50 in arr        
    for i in arr:        
        c[i] += 1 
    #find least max number       
    j, st =  0, (len(arr)-n) #count of max numbers in arr
    for m in range(50, -1, -1):   
        j += c[m]
        if j >= st:
            c[m] = j - st
            break #m contains least max number
    j = 0
    #put elements from arr upto n, less than m upto c counts
    for i in arr:
        if i <= m and c[i] > 0:
            o[j] = i 
            j += 1
            c[i] -= 1
        if j == n: #out has all n elements for out
            break
    return o

from bisect import bisect_left

def performant_smallest(arr, n):
    sarr = sorted(arr)
    limit = sarr[n-1]
    r = n - bisect_left(sarr, limit)
    ans = []
    for a in arr:
        if a < limit or (a == limit and r):
            ans.append(a)
            r -= (a == limit)
            if len(ans) == n:
                return ans


import numpy as np

def performant_smallest(arr, n):
    return np.asarray(arr)[np.sort(np.argsort(arr, kind='mergesort')[:n])].tolist()

def performant_smallest(arr, n):
    count = [0] * 51
    
    for num in arr:
        count[num] += 1
    
    take = [0] * 51
    i = 1
    
    while True:
        c = count[i]
        if c >= n:
            take[i] = n
            break
        else:
            take[i] = c
            n -= c
        i += 1
    
    res = []

    for num in arr:
        if take[num]:
            res.append(num)
            take[num] -= 1
    
    return res
    


from collections import Counter


def performant_smallest(arr, n):
    counts = Counter(arr)
    total = 0
    num_max = 0
    result = []
    for item, count in sorted(counts.items()):
        if total + count >= n:
            maximum = item
            max_max = n - total
            break
        total += count
    for element in arr:
        if element < maximum:
            result.append(element)
        elif element == maximum and num_max < max_max:
            result.append(element)
            num_max += 1
    return result