apple / swift-algorithms Goto Github PK
View Code? Open in Web Editor NEWCommonly used sequence and collection algorithms for Swift
License: Apache License 2.0
Commonly used sequence and collection algorithms for Swift
License: Apache License 2.0
We currently provide just one way to trim a collection:
extension BidirectionalCollection {
public func trimming(
while predicate: (Element) throws -> Bool
) rethrows -> SubSequence {
let start = try endOfPrefix(while: predicate)
let end = try self[start...].startOfSuffix(while: predicate)
return self[start..<end]
}
}
We should also provide ways to trim only the start of the collection (trimmingPrefix(while:)
, available to all collections), or only the end (trimmingSuffix(while:)
).
Furthermore, collections for which Self == SubSequence
should have mutating
variants using trim
as the base name. As an example, Collection
's popFirst()
from the standard library is implemented using the same constraint.
And finally, despite String
not being its own SubSequence
, String
should also have access to these mutating variants for the sake of convenience.
I would like to add a GitHub workflow to run the tests. I wanted to check-in first to see if this is wanted and if there are any requirements for it.
At a high level I would:
Are there any requirements for the machine and swift versions? Is it okay to run on 'macOS-latest' and use swift test --enable-test-discovery
to run the tests?
Thank you.
The standard library includes prefix
and suffix
methods that take a number of elements or an index, but only a prefix
method that takes a predicate. We should add a suffix(while:)
method to match prefix(while:)
for bidirectional collections.
Several of the sequence/collection wrappers provide public
access to the collection that they wrap, which can end up raising questions about substitutability and isn't strictly necessary. We should make all of these internal
, instead.
The documentation of chunked(by:)
states that the predicate is evaluated on consecutive elements. Experience and a naive look at the source are suggesting it is evaluated using the first element of the chunk instead of the previous one.
Let a: [Int] = [1,2,3,4,6,7,8,9]
("5" is missing). We want to chunk a
such as two consecutive elements are consecutive numbers (their difference is exactly 1).
[1,2,3,4,6,7,8,9].chunked(by: { $1 - $0 == 1 }) == [[1, 2, 3, 4], [6, 7, 8, 9]]
[1,2,3,4,6,7,8,9].chunked(by: { $1 - $0 == 1 }) == [[1, 2], [3, 4], [6, 7], [8, 9]]
Am I understanding the documentation incorrectly, or is there an inconsistency between the documentation and the expected behavior?
I remember scan(_:combine:)
not making the cut on the grounds of offering low utility. Is it possible for it to find a place here?
combinations(ofCount:)
not working in a command line app for the documented examples.
Swift Algorithms version: 0.0.2
Swift version: 5 (selected from build settings).
main
branch of this packageCreated a new command-line app with v 0.0.2 of the Algorithms Swift Package, successfully compiled. I am trying to use combinations(ofCount: )
but it doesn't seem to work. I've tried with String and Int arrays, but the result of the combo only includes the original array. I've pretty much followed the documentation word-for-word, with the example.
func algorithmCombinations(_ digits: [Int]) -> [Int] {
let combos = digits.combinations(ofCount:3)
var results = [Int]()
for combo in combos {
results.append(contentsOf: combo)
print(combo)
}
return results
}
let res = algorithmCombinations([3,6,2]) // prints [3,6,2]
Describe what you expect to happen.
[2,3,6],[2,6,3],[3,2,6],[3,6,2],[6,2,3],[6,3,2]
gets printed and returned.
Describe or copy/paste the behavior you observe.
let res = algorithmCombinations([3,6,2]) // prints and returns [3,6,2]
Our test suite contains the XCTAssertEqualSequences
function which tests whether two sequences have equal elements, either based on Equatable
conformance or using a custom predicate. It's currently implemented in terms of the elementsEqual
method on Sequence
which only returns whether or not the two sequences have equal elements.
For our purposes, when the two sequences are different, it would not only be useful to know that they are different, but also how they are different. Either the elements at the same position in the respective sequences aren't equal, or one of the sequences is shorter than the other one. XCTAssertEqualSequences
should be changed to log this information to make debugging a bit easier.
Summary:
Add ability to optionally also include the pair of the last element and the first element at the end of AdjacentPairs
.
Use Case:
For use with circular linked links. Today, I was working with the key view loop on macOS and needed to be able to tie the last element in the loop back to the first. AdjacentPairs
almost made this really easy, but was missing the pair of (last, first) so I couldn’t connect them together to be a loop.
for (previousView, nextView) in keyViewLoop.adjacentPairs(wrapping: true) {
previousView.nextKeyView = nextView
}
Possible API:
I’m not sure if this should be a separate API, or if this extends AdjacentPairs
extension Sequence {
/// …
/// The following example uses `adjacentPairs(wrapping: true)` to iterate over
/// adjacent pairs of integers:
///
/// for pair in (1...).prefix(5).adjacentPairs(wrapping: true) {
/// print(pair)
/// }
/// // Prints "(1, 2)"
/// // Prints "(2, 3)"
/// // Prints "(3, 4)"
/// // Prints "(4, 5)"
/// // Prints "(5, 1)"
@inlinable
public func adjacentPairs(wrapping: Bool = false) -> AdjacentPairsSequence<Self> {
AdjacentPairsSequence(base: self, wrapping: wrapping)
}
}
extension Collection {
/// …
/// for pair in (1...5).adjacentPairs(wrapping: true) {
/// print(pair)
/// }
/// // Prints "(1, 2)"
/// // Prints "(2, 3)"
/// // Prints "(3, 4)"
/// // Prints "(4, 5)"
/// // Prints "(5, 1)"
@inlinable
public func adjacentPairs(wrapping: Bool = false) -> AdjacentPairsCollection<Self> {
AdjacentPairsCollection(base: self, wrapping: wrapping)
}
}
Recently we've been exploring at FilePath APIs for Swift System, including extension
:
let path: FilePath = "/tmp/archive.tar.gz"
print(path.stem!)
print(path.extension!)
// Prints "archive.tar"
// Prints "gz"
For more complicated cases, a lazy version of the existing split
algorithm could be a handy and efficient (no heap allocations!) way to operate on a path with multiple extensions:
let path: FilePath = "/tmp/archive.tar.gz"
for component in path.basename!.string.lazy.split(separator: ".") {
print(component)
}
// Prints "archive"
// Prints "tar"
// Prints "gz"
Recently we've been exploring at FilePath APIs for Swift System, including extension
:
let path: FilePath = "/tmp/archive.tar.gz"
print(path.stem!)
print(path.extension!)
// Prints "archive.tar"
// Prints "gz"
For more complicated cases, a lazy version of the existing split
algorithm could be a handy and efficient (no heap allocations!) way to operate on a path with multiple extensions:
let path: FilePath = "/tmp/archive.tar.gz"
for component in path.basename!.string.lazy.split(separator: ".") {
print(component)
}
// Prints "archive"
// Prints "tar"
// Prints "gz"
Using the mutating partitioning functions are useful even when the returned index isn’t used.
The Embracing Algorithms (WWDC 2018) session implements a bringForward(elementsSatisfying:)
function on MutableCollection
.1 It uses stablePartition(by:)
in its implementation, but doesn’t need its return value, resulting in a warning.
extension MutableCollection {
mutating func bringForward(elementsSatisfying predicate: (Element) -> Bool) {
if let predecessor = indexBeforeFirst(where: predicate) {
self[predecessor...].stablePartition(by: { !predicate($0) }) // ⚠️ Result of call to 'stablePartition(by:)' is unused
}
}
}
extension MutableCollection {
mutating func bringForward(elementsSatisfying predicate: (Element) -> Bool) {
if let predecessor = indexBeforeFirst(where: predicate) {
self[predecessor...].stablePartition(by: { !predicate($0) })
}
}
}
While it could be argued that bringForward(elementsSatisfying:)
should return an Index
as well, even that return value isn’t always needed to be used and should be marked as @discardableResult
.
main
branch of this packageThis is a "subtract" operation, e.g.:
let animals = ["Cow", "Bulldog", "Labrador"]
return animals.without(["Bulldog", "Labrador"]) // ["Cow"]
We can see that this is an operation Swift developers are already trying to do from SO questions (1, 2), and it exists in other languages like Ruby.
This is a proposal to get consensus on it. And if people like it, I'd be happy to implement it.
swift-algorithms/Sources/Algorithms/Partition.swift
Lines 171 to 182 in e2fa131
In the documentation for partitioningIndex(where:)
, it only mentions what happens when the predicate returns true
. But, if the predicate
returns false
in all cases, it is unclear what the return value is. The documentation should be written so that it is clear that the return value is endIndex
if belongsInSecondPartition
returns false
for all elements.
I think this should at least be reflected in the “Returns” section of the inline documentation, but could probably be made more clear by rephrasing the first few sentences. The first sentence makes it sound like this is identical to firstIndex(where:)
, but the second and third sentences make the behavior more clear, indicating that this function is only to be used on collections that have already been partitioned.
The Collection.partitioningIndex(where:)
method is described in "Partition.md," the guide for its source file. However, the master list on the library home-page's read-me does not list this method. The read-me only lists the stable-partitioning methods in that same source file. The partitioningIndex
method should be listed in the read-me file. It needs to be in a different category, though.
In c++ there has a stl function named as lower_bound which works as binary search. But in swift there has no such function. Could you please add it?
I found myself often having to find the first element in an array that passes an optional initialiser.
If I wanted to stick to a purely functional paradigm (which I do, I'm a zealot) I need to do some pretty not-ideal transforms to allow this behaviour without defining a new function.
let value = ["Hello", "10"].lazy.map(Int.init).first { $0 != nil }.flatMap { $0 }
This could be trivialised with the following (naive) implementation.
public extension Sequence {
/// Returns the first element in `self` that `transform` maps to a `.some`.
func first<Result>(of transform: (Element) throws -> Result?) rethrows -> Result? {
for value in self {
if let value = try transform(value) {
return value
}
}
return nil
}
}
As I mentioned in #109, a benchmark suite is important for ensuring a stable level of performance.
Personally, I've been using https://github.com/google/swift-benchmark - it's a little rough around the edges, but it produces decent reports on all platforms and the dynamic iterations features works really well for getting stable readings out of small code snippets. I'd encourage Apple (or Swift.org) to adopt it, given S4TF's demise, the likelihood that the original authors will abandon it, and the need for good benchmarking utilities that work across platforms.
cycled(times:)
is currently implemented as follows:
extension Collection {
public func cycled(times: Int) -> FlattenSequence<Repeated<Self>> {
repeatElement(self, count: times).joined()
}
}
This is suboptimal because FlattenSequence
does not conform to RandomAccessCollection
when the base collection does, even though the return value of cycled(times:)
could! By implementing this method in terms of FlattenSequence
, we are essentially throwing away the information that each inner collection is the same (and therefore has the same length).
Another way of repeating a collection a fixed number of times is by taking the product of it and an integer range:
let array = [10, 20, 30]
for (_, x) in product(0..<5, array) {
print(x) // 10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30, 10, 20, 30
}
Unlike FlattenSequence
, the Product2
collection does conditionally conform to RandomAccessCollection
.
We should add a new FiniteCycle
collection as the return type of product(times:)
that wraps a Product2<Range<Int>, Base>
value and conforms to RandomAccessCollection
.
Replace this paragraph with a description of your proposed feature. Code samples that show what's missing, or what new capabilities will be possible, are very helpful! Provide links to existing issues or external references/discussions, if appropriate.
In the (only) implementation of XCTAssertUnorderedEqualSequences
(where elements are Equatable
), it converts the sequence into an Array
. Then it iterates through the second sequence, calling firstIndex(of:)
on the first array (O(n)), which totals to O(n2). If a Set
were used (when the elements are Hashable
), then getting the index of an element is O(1), which would make the total algorithmic complexity O(n).
XCTAssertUnorderedEqualSequences
is O(n) when Element: Hashable
XCTAssertUnorderedEqualSequences
is O(n2) when Element: Hashable
I regularly find myself wanting to sum all the (numeric) elements in a Set
, Array
or other Collection
s. This made me think about whether adding a simple wrapper in the standard library for the sum and product operations, something along the lines of:
collection.reduce(0,+)
for Sums
and
collection.reduce(0,*)
for Products
(only for collections where Element: Numeric
)
could be more clearer to write. In terms of implementation details, this is purely additive.
I don't know whether reduce
would be the best way to implement this, but would be open to feedback on this. Might be a good starter issue?
When doing macOS or iOS programming, a common use-case I have for interspersed
is to insert a separator or divider view in-between a bunch of other views.
Example, given an array of views, I'd like to insert a separator view in-between each one:
let views = [view1, view2, view3]
let allViews = views.interspersed(using: { SeparatorView() })
Expected:
[view1, separator1, view2, separator2, view3]
Because these are NSView, the inserted element needs to be a new instance each time, which the existing implementation does not appear to offer.
I have a daily CI that cross-compiles this package for Android along with swift-numerics trunk: it broke because of this update today.
Swift Algorithms version: main
branch, but only when forced to build against swift-numerics' latest commit.
Swift version: 5.4.2 and the latest 5.5 and trunk development snapshots
main
branch of this packageCheck out trunk of this package and swift-numerics and force this package to use that one by replacing the online checkout with .package(path: "../swift-numerics"),
.
Builds as normal.
error: product 'RealModule' not found in package 'swift-numerics'. it is required by package 'swift-algorithms' target 'Algorithms'.
Also, the current swift-numerics checkout of 0.0.1 that's normally used is two years old, should also update that.
One of the most common uses of compactMap
is to just flatten the nil
s out of a sequence without transforming its elements, i.e. x.lazy.compactMap { $0 }
.
A compacted()
convenience method for this use case would be useful because, similar to joined()
in the Standard Library, it wouldn't have to capture an escaping closure and (by the current conventions) it would be able to be lazy by default, i.e. x.compacted() // => Compacted<[Int?], Int>
A new Compacted
sequence should also be able to conditionally conform to Collection
and BidirectionalCollection
, and it should precompute on initialization in order to provide an O(1) startIndex
.
Here's a sketch of the Sequence
conformance:
struct Compacted<Base: Sequence, Element>: Sequence
where Base.Element == Element?
{
let base: Base
struct Iterator: IteratorProtocol {
var base: Base.Iterator
mutating func next() -> Element? {
while let wrapped = base.next() {
if let some = wrapped {
return some
} else {
// skip nil
}
}
return nil
}
}
func makeIterator() -> Iterator {
return Iterator(base: base.makeIterator())
}
}
extension Sequence {
func compacted<Unwrapped>() -> Compacted<Self, Unwrapped> where Element == Unwrapped? {
Compacted(base: self)
}
}
var tests: [[Int?]] = [
[],
[0],
[nil],
[0, nil],
[nil, 0],
[0, nil, 1, nil, 2, nil],
[0, 1, 2, nil, nil, nil],
[nil, nil, nil, 0, 1, 2],
]
for test in tests {
assert(test.compacted().elementsEqual(test.compactMap({ $0 })))
}
// let x: Array<Int> = [1, 2, 3]
// _ = x.compacted() // error: instance method 'compacted()' requires the types 'Int' and 'Unwrapped?' be equivalent
Thanks to @natecook1000 for coming up with how to make the types work out!
The implementation of the counts
property on Combinations
can be optimized to make use of the fact that the binomial is symmetrical around N/2 or (N - 1)/2.
More details available in this review comment on #51.
Just helps new starters to get started with how to contribute when opening a PR. I am happy to attempt this.
Screenshot of Contribution Guidelines hyperlink:
main
branch of this packageThe link should be (I think): https://github.com/apple/swift-algorithms/blob/main/CONTRIBUTING.md
Actual: https://github.com/apple/swift-algorithms/CONTRIBUTING.md <-- This is broken for #133
Open Markdown file for Contribution Guidelines.
Sorry if this is the wrong place to ask, but I didn’t know anywhere else to ask. 😂
I am a long time iOS Swift/ObjC developer and I have been looking to get involved contributing to this repo (I use it in a project currently) but looks like all the good-first-issue
labelled issues have been taken.
I wasn’t sure if the starter issue labels get updated on a regular basis (or if there is a Jira board that I don’t know about) so wanted to ask just in case (I am very keen). Are there any new features or improvements I could try to take as a good first issue?
Thanks a lot for the great work, and in advance for the help. Can’t wait to use this in the standard library when this becomes live! 😊
There seems to be broad appetite for sorting on, say, surnames or ages for a collection of Person
values. This has been made even more ergonomic now that key path literals can be used where a function takes a closure as an argument.
I'd propose, therefore, to add the following sorted(on:by:)
and sort(on:by:)
additions:
extension Sequence {
@inlinable
public func sorted<T>(
on transform: (Self.Element) throws -> T,
by areInIncreasingOrder: (T, T) throws -> Bool
) rethrows -> [Element] {
try sorted {
try areInIncreasingOrder(transform($0), transform($1))
}
}
@inlinable
public func sorted<T: Comparable>(
on transform: (Self.Element) throws -> T
) rethrows -> [Element] {
try sorted { try transform($0) < transform($1) }
}
}
extension MutableCollection where Self: RandomAccessCollection {
@inlinable
public mutating func sort<T>(
on transform: (Self.Element) throws -> T,
by areInIncreasingOrder: (T, T) throws -> Bool
) rethrows {
try sort {
try areInIncreasingOrder(transform($0), transform($1))
}
}
@inlinable
public mutating func sort<T: Comparable>(
on transform: (Self.Element) throws -> T
) rethrows {
try sort { try transform($0) < transform($1) }
}
}
The use site would look like the following:
struct Person {
var name: String
var age: Int
}
let persons = [
Person(name: "Alice", age: 56),
Person(name: "Bob", age: 34)
]
let x = persons.sorted(on: \.name, by: >)
let y = persons.sorted(on: \.age)
Any interest in such a change?
Xcode 14, target iOS is 14.1
When using a combinations in a playground, I get this error -
error: Test.playground:301:30: error: value of type '[Double]' has no member 'combinations' for combo in combos.combinations(ofCount: 1...4) {
Now where else to turn. It seems that the package is successfully added to the project. The playground is in the project with the dependancy added.
The import statement is there.
import Algorithms
Growl, not sure who else to ask?
With dictionaries, we have a uniquingKeysWith
parameter. It would be helpful to have similar for uniqued
.
This came up in a Stack Overflow Q/A. The following works but relies on arrays—we should have something better in Algorithms
.
import struct OrderedCollections.OrderedDictionary
public extension Sequence {
@inlinable func uniqued<Subject: Hashable>(
on projection: (Element) throws -> Subject,
uniquingWith combine: (Element, Element) throws -> Element
) rethrows -> [Element] {
try OrderedDictionary(keyed(by: projection), uniquingKeysWith: combine)
.values
.elements
}
}
public extension Sequence {
@inlinable func keyed<Key: Hashable>(
by key: (Element) throws -> Key
) rethrows -> [KeyValuePairs<Key, Element>.Element] {
try map { (try key($0), $0) }
}
}
randomSample
may have crash in case of 0
was out from Double.random(in: 0..<1)
.
log(0)
is invalid because the domain of log(x)
is 0 < x
.
It seems that Double.log(0.0)
produces -inf
.
(lldb) po Double.log(0.0)
-inf
-inf
cannot cast to Int
so the next crash happens.
Swift Algorithms version: 0.0.2
Swift version: Paste the output of swift --version
here
Apple Swift version 5.3.2 (swiftlang-1200.0.45 clang-1200.0.32.28)
Target: x86_64-apple-darwin19.6.0
main
branch of this packageI can reproduce this behavior from the code below.
var generator = SplitMix64(seed: 0x61c8864680b583eb) // this generator outs `0` first.
_ = c.randomSample(count: k, using: &generator) // crash!
Does not crash.
pasted screeenshot above.
Replace this paragraph with a short description of the incorrect incorrect behavior. If this is a regression, please note the last version that the behavior was correct in addition to your current version.
Swift Algorithms version:
main
branch
Swift version:
swift-driver version: 1.26.21 Apple Swift version 5.5.2 (swiftlang-1300.0.47.5 clang-1300.0.29.30)
Target: arm64-apple-macosx12.0
main
branch of this packageThe following code crashes:
import Algorithms
import Foundation
let input = "A|1|B|2"
let keyPairs = input
.split(separator: "|", omittingEmptySubsequences: false)
.chunks(ofCount: 2)
let aValue = keyPairs.first(where: {$0.first == "A"})
// .flatMap { Array($0) }
.flatMap { $0.count == 2 ? $0[1] : nil }
let bValue = keyPairs.first(where: {$0.first == "B"})
// .flatMap { Array($0) } // <--- uncomment this and it no longer crashes
.flatMap { $0.count == 2 ? $0[1] : nil } // <--- crash here with "Fatal error: Index out of bounds"
print("A: \(aValue ?? "n/a"); B: \(bValue ?? "n/a")")
It shouldn't crash. Each chunk has a count of 2 so accessing a chunk with index 1 should not crash.
It crashes. If I uncomment the conversion back to Array
it works fine. Based on some testing, the crash appears to happen with every sub-chunk after the first one.
Here's a checklist of the remaining work to do for the next Algorithms
release:
GitHub has lots of really handy bots that integrate with pushed commits and PR actions, as well as GitHub Actions CI. I have used GitHub’s bots in my own projects and found them very secure, helpful and easy to integrate.
I have raised #133 re: [ImgBot] but I am open to your feedback on more general Bot integrations as well.
Thanks.
While benchmarking a different project, I noticed that the compilation / type checking of StrideCollection.offsetBackward is the bottleneck when building swift-algorithms. On a 2019 8 Core MacBook Pro using Xcode 12.4 a small refactor reduced compiling Stride.swift from 6.5s -> 1s, so that it is no longer the bottleneck in the build graph.
Swift Algorithms version: 0.2.1
/ main
Swift version:
Apple Swift version 5.3.2 (swiftlang-1200.0.45 clang-1200.0.32.28)
Target: x86_64-apple-darwin19.6.0
main
branch of this packagexclogparser parse --project swift-algorithms --reporter html
to generate the screenshots below
targets: [
.target(
name: "Algorithms",
dependencies: [
.product(name: "RealModule", package: "swift-numerics"),
],
swiftSettings: [.unsafeFlags([
"-driver-time-compilation",
"-Xfrontend",
"-debug-time-compilation",
"-Xfrontend",
"-debug-time-function-bodies",
"-Xfrontend",
"-debug-time-expression-type-checking",
"-Xfrontend",
"-warn-long-function-bodies=500",
"-Xfrontend",
"-warn-long-expression-type-checking=500",
])]),
.testTarget(
name: "SwiftAlgorithmsTests",
dependencies: ["Algorithms"]),
]
Before | After |
---|---|
- let distance = i == endIndex
- ? -((base.count - 1) % stride + 1) + (n - 1) * -stride
- : n * -stride
+ // We typically use the ternary operator but that stresses out the compiler.
+ // To avoid slow build times for consumers, we use the longhand below.
+ let distance: Int
+ if i == endIndex {
+ distance = -((base.count - 1) % stride + 1) + (n - 1) * -stride
+ } else {
+ distance = n * -stride
+ }
Users build time shouldn't be unnecessarily impacted by using swift-algorithms.
Builds for consumers are slower than necessary. As swift-algorithms is likely to be early in a dependency graph, this is likely to affect users overall build times.
This code should be fast, but isn't:
for x in (0..<10_000_000).striding(by: 1_000_000) {
// ...
}
Stride
's iterator wraps the base collection's iterator, and can't skip over multiple elements at a time. By forcing the iterator to be an IndexingIterator
, the code is fast again:
for x in (0..<10_000_000).striding(by: 1_000_000)[...] {
// ...
}
I don't think we can vary the Stride.Iterator
associated type based on whether Base
conforms to Collection
, so the only way to fix this that I can think of is to split up Stride
into two types (with two overloads), one for sequences and one for collections.
I was playing around with your package and decided to take a look at a Windows example. After setting a very simple playground and trying this example, I can not build it. Instead of building it, it throws the next error:
/path/to/playground/main.swift:5:32: error: value of type 'String' has no member 'windows'
let windowed: [String] = swift.windows(ofCount: 2)
First of all, I thought that there is something on my end, however, other examples work fine(I've tried this and this)
Swift Algorithms version: 0.0.2
Swift version: Apple Swift version 5.3.2 (swiftlang-1200.0.45 clang-1200.0.32.28) Target: x86_64-apple-darwin20.3.0
main
branch of this packageHere is my Package.swift
:
import PackageDescription
let package = Package(
name: "playground",
dependencies: [
.package(url: "https://github.com/apple/swift-algorithms", from: "0.0.2"),
],
targets: [
.target(
name: "playground",
dependencies: [
.product(name: "Algorithms", package: "swift-algorithms"),
],
path: "Sources/playground"
),
]
)
and main.swift
:
import Foundation
import Algorithms
let swift = "swift"
let windowed: [String] = swift.windows(ofCount: 2)
print(windowed)
I expected to see the next result: ["sw", "wi", "if", "ft"]
I get the error after running swift build
:
/path/to/playground/main.swift:5:32: error: value of type 'String' has no member 'windows'
let windowed: [String] = swift.windows(ofCount: 2)
In #4 the implementation of trimmed(where:)
requires a raw loop because using lastIndex(where:)
would require making an extra call to index(after:)
to advanced the returned index.
The embracing algorithms talk exhibits the need for the dual—the index before firstIndex(where:)
—to avoid a raw loop or an extra call to index(before:)
:
extension MutableCollection {
mutating func bringForward(elementsSatisfying predicate: (Element) -> Bool) {
if let predecessor = indexBeforeFirst(where: predicate) {
self[predecessor...].stablePartition(isSuffixElement: { !predicate($0) })
}
}
}
extension Collection {
func indexBeforeFirst(where predicate: (Element) -> Bool) -> Index? {
return indices.first {
let successor = index(after: $0)
return successor != endIndex && predicate(self[successor])
}
}
}
These use cases seem like sufficient justification to add these algorithms.
Though I wonder if indexBeforeFirst(where:)
/indexAfterLast(where:)
or firstIndex(before:)
/lastIndex(after:)
or some other naming scheme is best?
The libray doesn't compile under Xcode 14 and iOS 16 beta 4
Swift Algorithms version: 1.0.0
main
branch of this packageNow we have randomSample
method for collections to get multiple random elements of a specific number with orders shuffled. This behavior should make it easy to make a shuffle method, which don't have to take any parameters (or a generator, if needed) to shuffle the collection. Inside the shuffle method, we just have to call randomSample(count: self.count)
and it should work as expected:
let aCollection = [1, 2, 3, 4, 5]
let shuffled = aCollection.shuffled()
// ↑ which should be identical with `aCollection.randomSample(count: aCollection.count)`
Hi!
TL;DR - permutations(ofCount:)
is slow in debug builds, taking tens of seconds vs explicit nested for loops taking a fraction of a second. Release builds are fine. Hopefully there's a way to mitigate this problem in debug builds so I can use the algorithm along with being able to use the debugger.
(also, in retrospect, I am confusing permutations and combinations, so I should have used combination here %-) It works fine in Debug-mode. But the issue still stands of the long time to do the permutation work in debug-land)
Using version 0.2.1
main
branch of this package. I have not, but notice that there aren't any changes since 0.2.1 was cutAttached is a project you can run. Look in ContentView.swift for aoc1_2
and use the #if
there to choose between the permutations
version and one that's nested for loops. Run and click the Permute button to run.
TL;DR:
From AdventOfCode 2020, day 1: https://adventofcode.com/2020/day/1 with a 200 element array. Find the triple of elements in the array that add to 2020, then return their product.
for perm in stuff.permutations(ofCount: 3) {
if perm[0] + perm[1] + perm[2] == 2020 {
let solution = perm[0] * perm[1] * perm[2]
print("FOUND IT \(solution)")
break
}
The permutations runs in amount of time similar to a simple for-loop equivalent
In Debug mode, it's two orders of magnitude slower, due of course to Swift's lack of optimizations to enhance debuggability. It'd be nice if it were possible to use this algorithm (maybe others? I haven't investigated any others yet) in a debuggable environment. Right now, waiting 25+ seconds for each edit/run/test/curse cycle is a long time.
In release mode, the times are short enough to where it doesn't impact workflow (outside of not being able to debug things outside of print statements)
Sample project:
Permutation.zip
Instruments profile of a Debug build.
Permutations-instruments.trace.zip . just a quick glance, a lot of time is spent in memory (nanov2) allocation
My timing results
// Xcode 12.2, MacBook Pro (16-inch, 2019), Catalina
// debug mode
// permutations - 22.7 seconds
// for loops - 0.25 seconds
// release mode
// permutations - 0.25 seconds
// for loops - 0.002 seconds
//
// Xcode 13-beta-1, M1 mini, Big Sur.
// debug mode
// permutations - 9.2 seconds
// for loops - 0.113 seconds
// release mode
// permutations - 0.127 seconds
// for loops - 0.001 seconds
It seems there is a compile time issue found in Release configuration for the latest release version 0.1.0 when trying to compile with Xcode. Debug configuration appears to be fine.
Swift Algorithms version: 0.1.0
Swift version: Paste the output of swift --version
here.
Apple Swift version 5.3.2 (swiftlang-1200.0.45 clang-1200.0.32.28)
Target: x86_64-apple-darwin19.6.0
Xcode Version: 12.4 (12D4e)
main
branch of this packageCreate a new iOS project in Xcode, add Swift Algorithms version 0.1.0 as a dependency. Attempt to archive the app -> see error.
App compiles with Xcode. I have not tested this outside of Xcode yet, will report back when I can, figured I'd post now.
IMO the port of the original Swift implementation made the name gratuitously worse. Aside from being precedented partitionPoint
is shorter and more wieldy, not any easier to misinterpret, a natural name (it was chosen totally independently for the algorithm in C++) and doesn't make the type name Index
more significant than it should be. The addition of ing
in particular turns what can be read as a pure noun—a thing—into something that is definitely the noun form of a verb—an action—thus making this algorithm seem like it has something to do with partitioning when it does not.
I noticed there’s a method for counting the unique permutations of a collection - how come there is no equivalent for combinations? For example the unique combinations of length 2 of “aabc” are “aa”, “ab”, “ac”, “bc”. If others think this would be useful Id be interested in trying to implement it !
An equivalent would be more_itertools.distinct_combinations(collection, k)
in Python
Thanks for this amazing framework ✌️.
Well, my request relates to the framework Charts which is very popular with more than 20k stars.
With the latest version, this framework has been integrated via SPM. However, this framework does not support CocoPods here. As a result, this popular framework can no longer be installed via Cocoapods.
I would therefore wish that this framework could also be integrated via CocoaPods.
The issue here is x86_64 simulator is not supported as it hinders development using SwiftUI project. This issue is there in every release.
You can reproduce this by adding settings in build settings
This setting is required other spm to compile.
When adding this setting simulator must compile and run.
Many iOS developer use cocoapods in their project. So i think it would be convenient if you add cocoapods feature.
Thanks
Some of the algorithms in this package have a return value that might not be needed by the caller. It would be nice if these were marked as @ discardableResult
so that callers don't have to use _ =
to silence Xcode warnings.
For example, stablePartition
returns the start of the resulting suffix, which might not be of interest to a caller who's only interested in the final result.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.