Python φιλτράρισμα λίστας

[albNik]

Εγω εδωσα μια εναλλακτική ιδεα (replace 010 με 000). Δεν ειναι θεμα αν ξερω python η οχι.

[tsofras]

40 λεπτά πριν, Heyho είπε

Το performance δεν το σκέφτηκα, εστίασα στο paradigm και τον αλγόριθμο. Συμφωνώ για το performance των vectorized operations. 

Τέλος, ίδια δεν είναι τα all, αλλά έχουν επανάληψη. Υλοποιούνται με επανάληψη. 

Εξήγησέ μου με ποιον τρόπο κάποιος βοηθάει τον ΟΡ όταν ο ίδιος παραδέχεται ότι δεν γνωρίζει αυτό για το οποίο ρωτάει ο ΟΡ. 

Πάτε καλά ορισμένοι; Μπαίνει κάποιος και ρωτάει κάτι πολύ συγκεκριμένο: Πώς μπορώ να κάνω κάτι ΣΤΗΝ ΓΛΩΣΣΑ PYTHON.

και το γράφει δύο φορές ότι είναι για Python. Μία στον τίτλο και μία στο κείμενο.

Πετάγεται ένας και απαντάει, λέγοντας μετά ότι δεν γνωρίζει Python, και πάτε και τον υπερασπίζεστε ότι και καλά «βοηθάει». Πώς; Πώς βοηθάει ΑΦΟΥ ΔΕΝ ΓΝΩΡΙΖΕΙ ΓΙΑ ΝΑ ΑΠΑΝΤΗΣΕΙ; Δεν το λέω εγώ ότι δεν γνωρίζει. ΤΟ ΕΙΠΕ Ο ΙΔΙΟΣ!

Πάτε καλά;

Εγώ σχολίασα την συμπεριφορά σου που ήταν απαράδεκτη για εμένα , άσχετα με την Python , μπορείς να κάνεις ακριβώς το ίδιο σχόλιο ποιο ευγενικά.

Και εγώ έχω σχολιάσει σε άλλες γλώσσες χωρίς να τις ξέρω λόγω αλγοριθμικής εμπειρίας , τι σημαίνει αυτό δεν θα έπρεπε? 

[pmav99]

@DIMITRISG για την ιστορία, αυτό που προσπαθείς να κάνεις συχνά είναι πιο εύκολο/κομψό να εκφραστούν σε functional γλώσσες όπως η scala και η Haskell. H python έχει κάποια functional στοιχεία, αλλά δεν είναι pure functional γλώσσα. Υπάρχουν βέβαια βιβλιοθήκες που βοηθούν στο να γράψεις functional κώδικα αλλά και πάλι στην πράξη υπάρχουν κάποιοι περιορισμοί. That being said, εκτός και αν έχεις ήδη μάθει να προγραμματίζεις σε functional paradigm, οι functional λύσεις πολύ πιθανόν να σου φαίνονται περισσότερο ακαταλαβίστικες.

Από εκεί και πέρα, αν οι πίνακες σου είναι πολύ μεγάλοι (πχ Ν > 1e6+) τότε αξίζει να δεις κάποια λύση με numpy. BTW οι λύσεις που έδωσα χτες είναι ενδεικτικές και λογικά σηκώνουν optimization, ιδίως αν παίξεις με καμιά cython. Αν πάλι οι πίνακες είναι πολύ μικροί (πχ Ν<100) τότε η σκέτη python είναι μάλλον γρηγορότερη (τα thresholds είναι από το μυαλό μου :P)

Αν θες να μείνεις σε σκέτη python τότε δύο εναλλακτικές προτάσεις είναι οι εξής:

1. Μία απλή generator function. Επί της ουσίας δεν διαφέρει με αυτό που έκανες και εσύ, με τη διαφορά ότι δεν δουλεύει inplace και ότι κάνει πιο σωστό handling των edge values. Δεδομένων των performance quirks της python (πχ ακριβά functional calls, ακριβά lookups etc) νομίζω ότι δύσκολα θα μπορέσεις να πας πολύ καλύτερα από πλευράς performance:

def fixup(lst):
    yield lst[0]
    for i, item in enumerate(lst[1:-1]):
        if item == 0:
            yield 0
        else:
            # Τα indices είναι αυξημένα κατά ένα γιατι το loop
            # ξεκινάει από το δεύτερο στοιχείο της λίστας
            if lst[i] == 0 and lst[i + 2] == 0:
                yield 0
            else:
                yield 1
    yield lst[-1]

lst = [0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1]
expected = [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1]

assert list(fixup(lst)) == expected

To πλεονέκτημα της προηγούμενης λύσης είναι ότι είναι straight-forward, και ότι είναι easy to write and easy to read.

Μια δεύτερη λύση η οποία είναι σαφώς πιο functional και περισσότερο generic καθώς δουλεύει και με οποιοδήποτε άλλο pattern αλλά και με μεγαλύτερα windows είναι η εξής:

from itertools import repeat, chain, islice

def sliding_window(lst, size=1):
    for i in range(size, len(lst) - size):
        yield lst[i - size:i + size + 1]

def pad_symmetric(iterable, size=1, padding=False):
    pad = repeat(padding)
    return chain(islice(pad, size), iterable, islice(pad, size))

def fixup_pattern(lst, pattern):
    for value, window in zip(lst, pad_symmetric(sliding_window(lst))):
        yield 0 if window == pattern else value
        
lst = [0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1]
expected = [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1]

assert list(fixup_pattern(lst, pattern=[0, 1, 0])) == expected

Το πλεονέκτημα της functional λύσης είναι ότι γίνεται composed από μικρές well defined functions για τις οποίες είναι πολύ εύκολο να γράψεις tests και τις οποίες μπορείς να χρησιμοποιήσεις και σε άλλες συναρτήσεις/projects.

Για την ιστορία η λύση με τη generator function είναι 2.5x γρηγορότερη (αυτό εξαρτάται βέβαια και από το πόσα 1 έχει η λίστα):

%timeit list(fixup(lst))
%timeit list(fixup_pattern(lst, pattern=[0, 1, 0]))

1.93 µs ± 32.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
4.86 µs ± 111 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

 

Επεξ/σία 8 Μαΐου 2019 από pmav99

[albNik]

μια  λυση για γλωσσες σαν τη c (χωρις if!)

 for(int i = 1; i < a.Length - 1; i++)
    a[i] *= a[i - 1] | a[i + 1];

 

Επεξ/σία 8 Μαΐου 2019 από albNik

[DIMITRISG]

Ευχαριστώ πολύ

Πολύ ενδιαφέρουσες όλες οι προτάσεις  γενικά η ανταλλαγή σκέψεων είναι πολύ εποικοδομητική και εκπαιδευτική.

Νομίζω ότι οι numpy και functional προσεγγίσεις είναι πιο κατάλληλες λόγω επιδόσεων (θα τις μετρήσω όλες για σύγκριση) και επειδή η λίστα ή πίνακας μπορεί ναι είναι πολύ μεγάλη (δεν το διευκρίνισα, πχ 90000 αντικείμενα ... ).

Θέλω να μείνω με Python διότι αφού δεν μπορώ να ασχοληθώ σε βάθος με τον προγραμματισμό και να αλλάζω τις γλώσσες σαν τα πουκάμισα, είπα να μείνω με μια και όταν μπορώ να ασχολούμαι αντί να πηγαίνω δεξιά αριστερά να εμβαθαίνω τις γνώσεις μου στην συγκεκριμένη γλώσσα και στον προγραμματισμό. Έτσι κι αλλιώς δεν έχω τίποτα εξειδικευμένες απαιτήσεις ούτως ώστε να χρειάζομαι και άλλες γλώσσες και δόξα το Θεό με την Python δεν μου έχει λείψει τίποτα (μάλιστα η δημοτικότητά της ολοένα και αυξάνεται)

[albNik]

Γενικα τα transformations δεν παιζουν καλα σε functional γλωσσες οταν το καθε στοιχειο της λιστας εξαρταται απο προηγουμενα/επομενα στοιχεια. Δεν μπορεις να αποφυγεις την αναφορα σε index  i,  i-1, i+1...

[solarpower]

a=[0,0,0,1,0,1,0,1,1,1,0,1]
print(a)
f=1
k=len(a)-1    
b=iter(a)
s=next(b)
while k>0 :
  t=next(b)
  k -= 1  
  if(f==0 and t==0):
    s=0
  print(s)
  f=s
  s=t
print(s)

Αυτή είναι η απάντηση.  Χρήση της iter() για οτιδήποτε iterable. Επίσης δουλεύει ακόμα και για μήκος 1.

Το κόλπο είναι να έχουμε ένα αρχικό στοιχείο 1, εδώ το f (first). μετά τραβάμε το πρώτο στην s (second) και πάμε στην while αν υπάρχουν άλλα στοιχεία.

Μέσα στη While τραβάμε το t (third) και μειώνουμε το k. Μετά κοιτάμε τα f και t και αν είναι μηδέν μηδενίζουμε το s.