nonbinary search part 2
Oct. 20th, 2016 06:07 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
juan_gandhiStats I got.
| dataset | size | boosted search | standard binary |
|---|---|---|---|
| Sine | 10000 | 9.00 | 15.36 |
| Cantor Set | 1025 | 16.00 | 17.86 |
| Convex/concave | 218983 | 4.52 | 6.45 |
| Concave | 109990 | 4.96 | 5.00 |
| Linear | 50000 | 3.00 | 15.36 |
| Convex | 108993 | 3.60 | 5.00 |
| Concave | 10002 | 3.71 | 4.10 | I count the average number of comparisons now. There's a challenge, implementing linear interpolation for strings, for instance. Doable, I guess. Thanks a lot for the idea of the integral of Cantor Set. It helped a lot to improve the algorithm.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2016-10-21 03:15 am (UTC)Why? They are base-256 numbers, all of the same alleged very large length, with implied 0s at the end.
no subject
Date: 2016-10-21 05:47 am (UTC)no subject
Date: 2016-10-21 07:14 am (UTC)no subject
Date: 2016-10-21 09:19 am (UTC)no subject
Date: 2016-10-21 02:35 pm (UTC)А вещественные поделить тоже фигня. Вот трансформировать строку в вещественное, это надо как-то насобачиться.
no subject
Date: 2016-10-21 03:39 pm (UTC)Рассмотрим набор aaa...aaa, aaa...aaб, ааа...аая, я, где букв а достаточно много, чтобы сделать численные представления строк одинаковыми.
Допустим, мы ищем ааа...ааю. Тогда у нас честный пропорциональный поиск превратится в линейный. Чтобы этого избежать, проверяемая позиция должна отстоять от края интервала не менее чем на какую-нибудь долю.
Ну и более или менее очевидное, но еще вопрос, насколько существенное на современных архитектурах: если мы помним, по какому количеству символов совпадают границы, то сравнивать будет нужно меньше.
no subject
Date: 2016-10-21 03:59 pm (UTC)no subject
Date: 2016-10-21 04:06 pm (UTC)no subject
Date: 2016-10-21 05:37 pm (UTC)no subject
Date: 2016-10-23 01:20 am (UTC)https://ru.wikipedia.org/wiki/Soundex