454720c27e
Improved ArrayList performance by removing size field. ( #255 )
...
* Improved ArrayList performance by removing `size` field.
Removed the `size` field from the `List` struct and replaced it with the built-in Go slice length implementation.
+ Achieved an average reduction of nearly 40% in execution time for `ArrayListGet`.
+ Achieved an average reduction of nearly 23% in memory usage for `ArrayListAdd`.
+ However, this change slightly increased the execution time for `ArrayListAdd` by 2.7%.
```
goos: linux
goarch: amd64
pkg: github.com/emirpasic/gods/v2/lists/arraylist
cpu: Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
│ old.txt │ new.txt │
│ sec/op │ sec/op vs base │
ArrayListGet100-8 51.20n ± 0% 32.49n ± 0% -36.53% (n=50)
ArrayListGet1000-8 447.5n ± 0% 270.3n ± 1% -39.60% (n=50)
ArrayListGet10000-8 4.418µ ± 1% 2.540µ ± 0% -42.52% (n=50)
ArrayListGet100000-8 44.06µ ± 0% 25.15µ ± 0% -42.91% (n=50)
ArrayListAdd100-8 726.5n ± 1% 760.5n ± 0% +4.69% (p=0.000 n=50)
ArrayListAdd1000-8 7.437µ ± 2% 7.389µ ± 1% ~ (p=0.746 n=50)
ArrayListAdd10000-8 70.06µ ± 1% 74.34µ ± 1% +6.11% (p=0.000 n=50)
ArrayListAdd100000-8 740.2µ ± 1% 728.9µ ± 2% ~ (p=0.147 n=50)
ArrayListRemove100-8 233.8n ± 0% 233.9n ± 0% ~ (p=0.162 n=50)
ArrayListRemove1000-8 2.275µ ± 0% 2.276µ ± 0% ~ (p=0.452 n=50)
ArrayListRemove10000-8 22.75µ ± 0% 22.75µ ± 0% ~ (p=0.956 n=50)
ArrayListRemove100000-8 1.323m ± 1% 1.331m ± 1% ~ (p=0.120 n=50)
geomean 7.218µ 6.119µ -15.22%
│ old.txt │ new.txt │
│ B/op │ B/op vs base │
ArrayListGet100-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListGet1000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListGet10000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListGet100000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListAdd100-8 2.987Ki ± 0% 2.087Ki ± 1% -30.14% (n=50)
ArrayListAdd1000-8 27.50Ki ± 1% 23.31Ki ± 2% -15.24% (p=0.000 n=50)
ArrayListAdd10000-8 293.9Ki ± 1% 204.7Ki ± 1% -30.36% (n=50)
ArrayListAdd100000-8 2.667Mi ± 1% 2.244Mi ± 12% -15.86% (p=0.000 n=50)
ArrayListRemove100-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListRemove1000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListRemove10000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListRemove100000-8 453.5 ± 1% 457.5 ± 1% ~ (p=0.059 n=50)
geomean ² -8.38% ²
¹ all samples are equal
² summaries must be >0 to compute geomean
│ old.txt │ new.txt │
│ allocs/op │ allocs/op vs base │
ArrayListGet100-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListGet1000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListGet10000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListGet100000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListAdd100-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListAdd1000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListAdd10000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListAdd100000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListRemove100-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListRemove1000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListRemove10000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
ArrayListRemove100000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=50) ¹
geomean ² +0.00% ²
¹ all samples are equal
² summaries must be >0 to compute geomean
```
* Improve ArrayList Remove() by `slices.Delete`
The performance of `slices.Delete()` is better
```
goos: linux
goarch: amd64
pkg: github.com/emirpasic/gods/v2/lists/arraylist
cpu: Intel(R) Core(TM) i7-4790 CPU @ 3.60GHz
│ old-remove.txt │ new-remove.txt │
│ sec/op │ sec/op vs base │
ArrayListRemove100-8 234.2n ± 1% 211.2n ± 2% -9.82% (p=0.000 n=10)
ArrayListRemove1000-8 2.293µ ± 1% 2.063µ ± 4% -10.05% (p=0.000 n=10)
ArrayListRemove10000-8 22.78µ ± 1% 20.53µ ± 2% -9.86% (p=0.000 n=10)
ArrayListRemove100000-8 1.318m ± 3% 1.279m ± 2% -2.96% (p=0.019 n=10)
geomean 11.27µ 10.34µ -8.22%
│ old-remove.txt │ new-remove.txt │
│ B/op │ B/op vs base │
ArrayListRemove100-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=10) ¹
ArrayListRemove1000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=10) ¹
ArrayListRemove10000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=10) ¹
ArrayListRemove100000-8 452.0 ± 4% 444.5 ± 1% ~ (p=0.224 n=10)
geomean ² -0.42% ²
¹ all samples are equal
² summaries must be >0 to compute geomean
│ old-remove.txt │ new-remove.txt │
│ allocs/op │ allocs/op vs base │
ArrayListRemove100-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=10) ¹
ArrayListRemove1000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=10) ¹
ArrayListRemove10000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=10) ¹
ArrayListRemove100000-8 0.000 ± 0% 0.000 ± 0% ~ (p=1.000 n=10) ¹
geomean ² +0.00% ²
¹ all samples are equal
² summaries must be >0 to compute geomean
```
* Improve ArrayList Clear() by using built-in clear() instead of creating a new one
* Refactor code by `slices` package.
* Refactor ArrayList Insert() by `slices.Insert()`
2024-07-18 09:41:44 -07:00
14f714261f
Generics migration ( #237 )
...
* Generics migration
This attempts to migrate this library in the least invasive way by preserving as
much of the original API as possible. It does not change the tests in a
meaningful way nor does it attempt to upgrade any logic that can be simplified
or improved with generics. This is purely an API migration, and still requires a
lot of additional work to be fully ready.
* Fix a few broken tests around serialization
* Add v2 suffix
* Temporarily change mod name for testing
* Rename module to /v2
2024-01-06 16:06:17 -08:00
b486cc91bf
Fix in ArrayList.Contains function against nil values
2022-04-18 20:14:01 +02:00
41012c6c58
Improve code coverage
2022-04-13 16:52:21 +02:00
e2b92bbc7a
Interface implementation assertions moved outside the functions
2022-04-13 15:04:39 +02:00
1f0b87f0e1
Implements json.Marshaler and json.Unmarshaler interfaces
2022-04-12 04:31:44 +02:00
b5735bcc4d
Merge pull request #165 from yvvlee/feature/implements_jsonMarshaler_and_Unmarshaler
...
Implements json.Marshaler and json.Unmarshaler interfaces
2022-04-12 03:58:15 +02:00
08ae493e8a
Implement NextTo and PrevTo for all iterators and containers (index or key, forward-only or reversable)
2022-04-12 01:20:56 +02:00
c9a2dcad62
Implements json.Marshaler and json.Unmarshaler
2021-04-08 15:19:55 +08:00
edc20eca0a
- fix arraylist test
2020-01-13 17:12:56 +08:00
1befeeefc9
- fix comments
2018-09-20 23:55:51 +02:00
c6630349c4
- bulk initialization for lists
2018-09-20 18:40:32 +02:00
cbce439b4e
Merge pull request #61 from Spriithy/feature/list_constructors
...
Added bulk constructors for arraylists & (doubly)-linked-lists
2018-09-20 18:23:21 +02:00
17852f48a5
- update documentation and comments
2018-09-20 17:44:34 +02:00
843fdb4848
Added Set(index, value) method to all Lists ( closes #86 )
...
Added tests
2018-09-19 14:41:47 -04:00
8557a87b9f
fmt
2018-09-19 05:05:43 +02:00
6f0f602e3e
Merge pull request #76 from xtutu/master
...
optimize array list
2018-09-19 04:55:21 +02:00
65869799a0
Revert "Revert "gofmt""
2018-06-18 13:13:01 +02:00
076c527d93
Revert "gofmt"
2018-06-17 14:41:40 +02:00
55e94ab1e3
all: gofmt
...
Run standard gofmt command on project root.
- go version go1.10.3 darwin/amd64
Signed-off-by: ia <isaac.ardis@gmail.com >
2018-06-17 01:02:33 +02:00
5d06966e29
optimize array list
2018-06-12 13:41:35 +08:00
f246a54621
Add IndexOf method to ArrayList
2017-12-26 19:18:50 +05:30
12451bdcc6
Added bulk constructors for arraylists & (doubly)-linked-lists
2017-09-28 14:22:00 +02:00
0dcb10bcab
- JSON serialization for all lists
2017-03-06 01:05:01 +01:00
efcbbe6274
- detailed extensive tests with breakdown on number of elements
2016-07-16 04:40:16 +02:00
213367f1ca
- replace long bsd text with short in all .go files
2016-06-27 04:21:09 +02:00
20229603ab
- refactor all iterators and enumerables into separate files
2016-06-27 04:02:52 +02:00
02f40db0cf
- test iterator end on reverse-iterable data structures
...
- fix red-black tree
2016-06-27 02:42:05 +02:00
f052c96069
- iterator end on reverse-iterable data structures
2016-06-27 00:41:32 +02:00
57162feff5
- rename Reset() to Begin() in iterators (this will allow End() which will make reverse loops more readable)
2016-06-27 00:08:01 +02:00
cbc23a5b79
- test iterator first on all iterable data structures
2016-06-26 23:58:23 +02:00
bdfeab4912
- iterator first on all structures with reversible iterators
2016-06-26 22:50:14 +02:00
3d1014bf63
- test iterator last on all structures with reversible iterators
2016-06-26 22:40:49 +02:00
f8b0747409
- iterator last on all structures with reversible iterators
2016-06-26 22:27:08 +02:00
3a938233a0
- test iterator reset on all structures
2016-06-26 21:44:23 +02:00
b86d413e66
- iterator reset on all structures
2016-06-26 20:50:49 +02:00
d7a31571cc
- add reversible iterators to lists (array list and doubly-linked list)
...
- documentation and tests updates
2016-06-25 18:17:48 +02:00
59bebe43ce
- update all documentation to be in godoc style
2016-06-25 17:02:21 +02:00
2ccfba5f93
- replace timsort with go's sort
2016-06-25 05:51:41 +02:00
ef9baa808a
- golint
2016-06-24 21:52:16 +02:00
35457aba81
- fix spelling
2016-06-24 20:27:34 +02:00
616c850bff
- refactor list's tests
2016-06-24 19:17:50 +02:00
544abaeab1
- remove map and select functions from enumerable interface, because this requires type assertions in chaining, which is really ugly and unnecessary. the only drawback is that one might forget to implement those functions and interface implementations asserts will not register that. (need help on this)
2016-06-24 06:20:24 +02:00
8cb4635c2c
- code document all enumarable functions and iterators in containers
2016-06-24 00:08:04 +02:00
3b6a40775a
- split enumerables into enumerables with keys and with indexes (same was done for iterators)
2016-06-22 21:03:51 +02:00
e4c3d8a0d8
- split iterators into two type (iterator with index and iterator with key)
2016-06-22 19:59:08 +02:00
60c2f3af71
- add enumerable and iterator to doubly linked list
2016-06-22 05:26:48 +02:00
c685593e6e
- rewrite enumerable operations using iterator (for easier copy/paste into other containers)
2016-06-22 05:11:41 +02:00
549ece1100
- iterator implementation
...
- tests for arraylist enumerable operations
2016-06-22 04:53:38 +02:00
6fefe7cc24
- iterator tests
...
- container_test fix
2016-06-22 03:42:35 +02:00
Kashiwa
Paul Chesnais
Emir Pasic
mshadow
yuanjin
Blake Miner
ia
xtutu
Mahadev
Spriithy
Emir Pasic