From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <zsh-users-return-21545-mason-zsh=primenet.com.au@zsh.org>
Received: (qmail 26096 invoked by alias); 10 May 2016 18:11:48 -0000
Mailing-List: contact zsh-users-help@zsh.org; run by ezmlm
Precedence: bulk
X-No-Archive: yes
List-Id: Zsh Users List <zsh-users.zsh.org>
List-Post: <mailto:zsh-users@zsh.org>
List-Help: <mailto:zsh-users-help@zsh.org>
X-Seq: 21545
Received: (qmail 22552 invoked from network); 10 May 2016 18:11:48 -0000
X-Spam-Checker-Version: SpamAssassin 3.4.1 (2015-04-28) on f.primenet.com.au
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,T_DKIM_INVALID
	autolearn=ham autolearn_force=no version=3.4.1
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=brasslantern-com.20150623.gappssmtp.com; s=20150623;
        h=from:message-id:date:in-reply-to:comments:references:to:subject
         :mime-version;
        bh=2Uh+Kv/zGEgjlOOBF5+dLwEJVpjNh84AhTfjoDM+i/Q=;
        b=UVlOsjWeYresqcqmV7ptrlZps2jdsHqk78M/TRjqZBw2AGUl3OXohcBelp2YO2ITYG
         IVgngDA33QQ41Otswdh0HRWWC2ppGb0O9yVvV3N9u75akFoNvCtwSXn55eDOPNZV5LLo
         huJQsrBlkaFZJaK3QKBXBimj/VijgELESfPhRLZX5VH2mKfhBQlnODjm86XKU7W6+L4+
         8D6WyqPF8gV/mmDesybvt4wjTAJpKGzvqgZDv4bRz2Jmyn2Fr9RNh/eAc1O/I5vI004B
         fiRGvBomiO67yX7J0uMB1R8URxLdekYc/XKtX80qi+0j5cgxzs2DzSQx6KRNGz08Gol/
         oJ6Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20130820;
        h=x-gm-message-state:from:message-id:date:in-reply-to:comments
         :references:to:subject:mime-version;
        bh=2Uh+Kv/zGEgjlOOBF5+dLwEJVpjNh84AhTfjoDM+i/Q=;
        b=V7UxyM0pP9lNt4SoTN5TAjHRZlkqu1GU9rqhw+PYUfAmBmJ7zP3V6ruD/tm4QTPxNs
         36Cgbw16biUnj1pQCWVr2705P/PC2+MfiWE1COAUg3TZJAqYq1P69WUadloNt++4w6kq
         W6hVjsx/EigD14V38pdz1Xw3F29pH7RA2l+VGHZ5th+nBjXwLpeZJi2DnTcHcscTYxvH
         NeR8+zvZe/KBJCxggJaaJRQ9iGipmQCl1R0lxPjhOfj9A1R7y0eUiUNJBE3eDeTLe1rm
         c1bwa3KZZvbHBWQP0LQrvn9qYiaaFxTa6FTNFoej936X4aRKjP7C3VevVSc2bqSUJgPQ
         3CgQ==
X-Gm-Message-State: AOPr4FUkKz23p5JcX5Vwd47k24Fa5BRHPBoJ50MPHrOZSl220s7iCeO6817YoyabZTGA7A==
X-Received: by 10.98.24.88 with SMTP id 85mr61380669pfy.52.1462903905148;
        Tue, 10 May 2016 11:11:45 -0700 (PDT)
From: Bart Schaefer <schaefer@brasslantern.com>
Message-Id: <160510111236.ZM1388@torch.brasslantern.com>
Date: Tue, 10 May 2016 11:12:36 -0700
In-Reply-To: <CAKc7PVBHuo8Hqu3fs_kLfW-hPG58DrVhZgPE24s3zHq09ndH6g@mail.gmail.com>
Comments: In reply to Sebastian Gniazdowski <sgniazdowski@gmail.com>
        "Re: Why approximate pattern doesn't match?" (May 10,  7:29pm)
References: <CAKc7PVB5XaTEgZ-k5dE1T1Fh1RVPR53zskRm0x9g8SeecZo-jw@mail.gmail.com> 
	<CAKc7PVBxQCb_-2pKSKqGbmw0xMcz20vJvQfVwa2RQYV3C2twzA@mail.gmail.com> 
	<160509205620.ZM17429@torch.brasslantern.com> 
	<CAKc7PVDehshzVeEueG9vuRb871bj824CZaby=WpowEK8EGUpxg@mail.gmail.com> 
	<20160510160518.2caebd70@pwslap01u.europe.root.pri> 
	<CAKc7PVAFi45NbfXfn4t6yGjbpnzL=bd-+9dH6f97jzrG-EksnQ@mail.gmail.com> 
	<20160510164028.60bfbee0@pwslap01u.europe.root.pri> 
	<CAKc7PVA-eq36xOmXOnEwfYTSEKy62GrQjPibWVHr1D1kEAX15A@mail.gmail.com> 
	<CAKc7PVBHuo8Hqu3fs_kLfW-hPG58DrVhZgPE24s3zHq09ndH6g@mail.gmail.com>
X-Mailer: OpenZMail Classic (0.9.2 24April2005)
To: Zsh Users <zsh-users@zsh.org>
Subject: Re: Why approximate pattern doesn't match?
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii

On May 10,  7:29pm, Sebastian Gniazdowski wrote:
}
} What's interesting is that this (doing ${a//(#a1)a|(#a1)b|...}) is
} painfully slow when compared to *~^* and :#, it works slower for 25
} elements than :# works for 5000.

As Mikael pointed out, ~^ is "and", whereas | is "or" -- for the "or"
case you have to compare every possibility to every array element, but
for the "and" case you can rapidly discard elements that don't match
the initial pattern.  It's not quite O(n*m) vs. O(n) but is in that
ballpark.