|
|
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
Няшик, Запили обычный RawByteString из файла и Pos - он сработает быстрее, тем более под x86. А можно сделать ещё быстрее с SSE и применением пары алгоритмов. Насколько я понял, у ТС задача поиска сразу нескольких слов в файле и при нахождении - замена. Все акцентируют своё внимание на поиске, хотя скорее всего проседает замена :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 09:49 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, если нужно несколько фраз сильно быстрее искать 'деревом'. Все фразы представляются как дерево ветвления. Сравнивается первый байт каждой фразы с 'текущим', далее идёт ветвление, либо на выход, если ничего не нашлось, либо на конкретную фразу. Что-то наподобие как lzw работает по своим справочникам. Ну и 'линейный' поиск стоит оптимизировать. Должно на 9 мб искаться моментально. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 10:00 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
makhaon, Да, тут уже предлагали Ахо-Карасика Только лучше не дерево, а хеш И хеш по первому символу - array[Char] ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 10:30 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
НяшикЗачем он ищет в файлах ? И что это, за файлы ??? Что - то вроде архива???? А ты тред с самого начала почитать не пробовал? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 12:39 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Опять про хэши..... Не могут быть хэши быстрее, так как - мы генерируем хэш для искаемого слова. И генерируем для сравнения. По этому я в своём интерпретаторе использовал древовидный вид поиска лексем, как предложил выше makhaon Док, Сложно... Чтение не моё ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 13:29 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
Няшик, А кто виноват в том, что ты не умеешь хеши использовать? Хеши в разы быстрее дерева. Тем более, если речь идёт о символах. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 14:00 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUНяшик, А кто виноват в том, что ты не умеешь хеши использовать? Хеши в разы быстрее дерева. Тем более, если речь идёт о символах. Приведи пример - что ты имеешь введу под поиском - хэшом Если ты собираешься сравнивать хэш, то ты должен для каждой N+1 генерировать новый хэш. Для искаемой строки. Куда быстрее, чем просто сравнить .... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 14:06 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
Няшик, Я уже раза 3 написал про массив от первого символа И про алгоритм Ахо-Карасика А твоё дерево лексем - это бред. С точки зрения оптимизации конечно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 14:15 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, А где там про хэш хоть слово ? https://ru.wikipedia.org/wiki/Алгоритм_Ахо_—_Корасик SOFT FOR YOUА твоё дерево лексем - это бред. С точки зрения оптимизации конечно. Посмотри что генерируют yacc в связке с bsion. Куча goto + switch ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 15:26 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
Няшик, У меня у самого есть суперкрутая утилита CachedSerializer, генерирующая case, и работающая со скоростью света. Но этот подход хорош тогда, когда перечень строковых констант изначально предопределён и длина идентифицируемой строки в момент поиска известна. В ситуации, когда в текстовом потоке мы выхватываем "лексемы", эта схема не работает, т.к. лексема и её длина зависит от последовательности символов. В этом случае актуален Ахо-Карасик, только подход при идентификации символов может быть разный. Можно делать полный перебор, поиск в сортированном массиве, дерево (и для заранее определённых констант можно написать case), но быстрее хешей всёравно ничего не будет. В твоём компиляторе, к примеру, можно существенно ускорить идентификацию лексем до 3 символов за раз с помощью таблиц(хеш). И я хотел это продемонстрировать, только ты из своей же ветки почему-то заблаговременно слился. Такое впечатление, что ты не компилятор пишешь, а рекламируешь дельфовый case. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 15:56 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Ну так приведи поиск по хэшам. Мб готовая реализации уже есть на том же гите ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 17:08 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOUНяшик, В твоём компиляторе, к примеру, можно существенно ускорить идентификацию лексем до 3 символов за раз с помощью таблиц(хеш). И я хотел это продемонстрировать, только ты из своей же ветки почему-то заблаговременно слился. Такое впечатление, что ты не компилятор пишешь, а рекламируешь дельфовый case. У меня всё равно git. Один и тот же файл, два раза никак не перекомпилируется, если не был изменён. (И нет, он не будет весь компилировать. Только те участки, которые были изменены и добавлены) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 17:10 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
Няшик, Ты просто не знаешь, как пользоваться хешами И да, тебе с самого начала говорили, что не нужно заморачиваться на скорости трансляции скриптов, значительно важнее скорость исполнения ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 17:18 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Да ты можешь наконец привести своё этакое чудо на хэшах? Или слился (Слился - слился, по настоящему) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 17:25 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
Няшик, Да не вопрос Приведи в качестве примера штук 20 своих лексем и напиши функцию, которая будет анализировать RawByteString и вызывать калбеки с описанием найденного. А я сделаю то же самое через хеши с упрощённой реализацией ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 17:33 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Няшик, на чё спорите? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 17:39 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan), На пинок :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 18:07 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan), Да не на что. Прощу привести пример, нет - же... .... Вот те пример из 21 правда. Но ничё. Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. 160. 161. 162. 163. 164. 165. 166. 167. 168. 169. 170. 171. 172. 173. 174. 175. 176. 177. 178. 179. 180. 181. 182. 183. 184. 185. 186. 187. 188. 189. 190. 191. 192. 193. 194. 195. 196. 197. 198. 199. 200. 201. 202. 203. 204. 205. 206. 207. 208. 209. 210. 211. 212. 213. 214. 215. 216. 217. 218. 219. 220. 221. 222. 223. 224. 225. 226. 227. 228. 229. 230. 231. 232. 233. 234. 235. 236. 237. 238. 239. 240. 241. 242. 243. 244. 245. 246. 247. 248. 249. 250. 251. 252. 253. 254. 255. 256. 257. 258. 259. 260. 261. 262. 263. 264. 265. 266. 267. 268. 269. 270. 271. 272. 273. 274. 275. 276. 277. 278. 279. 280. 281. 282. 283. 284. 285. 286. 287. 288. 289. 290. 291. 292. 293. 294. 295. 296. 297. 298. 299. 300. 301. 302. 303. 304. 305. 306. 307. 308. 309. 310. 311. 312. 313. 314. 315. 316. 317. 318. 319. 320. 321. 322. 323. 324. 325. 326. 327. 328. 329. 330. 331. 332. 333. 334. 335. 336. 337. 338. 339. 340. 341. 342. 343. 344. 345. 346. 347. 348. 349. 350. 351. 352. 353. 354. 355. 356. 357. 358. 359. 360. 361. 362. 363. 364. 365. 366. 367. 368. 369. 370. 371. 372. 373. 374. 375. 376. 377. 378. 379. 380. 381. 382. 383. 384. 385. 386. 387. 388. 389. 390. 391. 392. 393. 394. 395. 396. 397. 398. 399. 400. 401. 402. 403. 404. 405. 406. 407. 408. 409. 410. 411. 412. 413. 414. 415. 416. 417. 418. 419. 420. 421. 422. 423. 424. 425. 426. 427. 428. 429. 430. 431. 432. 433. 434. 435. 436. 437. 438. 439. 440. 441. 442. 443. 444. 445. 446. 447. 448. 449. 450. 451. 452. 453. 454. 455. 456. 457. 458. 459. 460. 461. 462. 463. 464. 465. 466. 467. 468. 469. 470. 471. 472. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 18:14 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
Выкладываю полный код моего генератора Код: php 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 18:16 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
Это старый генератор, и не жалко его сливать. В новом я всё под move переделал. К примеру Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 18:25 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
Няшик, Приведи в качестве примера штук 20 своих лексем и напиши функцию, которая будет анализировать RawByteString и вызывать калбеки с описанием найденного. Я что-то не вижу тестового проекта и оговоренной функции. Проверять корректность и замерять производительность мы на чем будем? На заднице? ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 18:27 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
Замеряйте как угодно и на чём угодно, но в исходном топике (Няшика или чей он там был), а не тут. Posted via ActualForum NNTP Server 1.5 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 18:44 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
Гаджимурадов Рустам, В других случаях я бы с тобой согласился, ибо против офтопика. Но в данном случае ситуация Ахо-Корасика (т.е. ситуация ТС) в чистом виде. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 18:48 |
|
||
|
Поиск последовательности в бинарном массиве
|
|||
|---|---|---|---|
|
#18+
SOFT FOR YOU, Вот проект. Тестируемый файл на 9,38 МБ (9 842 560 байт) 29120 строк с содержимым isset return if goto === require_once and var protected use => __DIR__ >= endswitch >> __CLASS__ >> endwhile list === == = >>= > JUTRJHIROTJHOTBHNIkoorth iyko hjisset return if goto === require_once and var protected use => __DIR__ >= endswitch >> __CLASS__ >> endwhile list === == = >>= > JUTRJHIROTJHOTBHNIkoorth iyko hj Время : 0,040280 Код проекта Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65. 66. 67. 68. 69. 70. 71. 72. 73. 74. 75. 76. 77. 78. 79. 80. 81. 82. 83. 84. 85. 86. 87. 88. 89. 90. 91. 92. 93. 94. 95. 96. 97. 98. 99. 100. 101. 102. 103. 104. 105. 106. 107. 108. 109. 110. 111. 112. 113. 114. 115. 116. 117. 118. 119. 120. 121. 122. 123. 124. 125. 126. 127. 128. 129. 130. 131. 132. 133. 134. 135. 136. 137. 138. 139. 140. 141. 142. 143. 144. 145. 146. 147. 148. 149. 150. 151. 152. 153. 154. 155. 156. 157. 158. 159. 160. 161. 162. 163. 164. 165. 166. 167. 168. 169. 170. 171. 172. 173. 174. 175. 176. 177. 178. 179. 180. 181. 182. 183. 184. 185. 186. 187. 188. 189. 190. 191. 192. 193. 194. 195. 196. 197. 198. 199. 200. 201. 202. 203. 204. 205. 206. 207. 208. 209. 210. 211. 212. 213. 214. 215. 216. 217. 218. 219. 220. 221. 222. 223. 224. 225. 226. 227. 228. 229. 230. 231. 232. 233. 234. 235. 236. 237. 238. 239. 240. 241. 242. 243. 244. 245. 246. 247. 248. 249. 250. 251. 252. 253. 254. 255. 256. 257. 258. 259. 260. 261. 262. 263. 264. 265. 266. 267. 268. 269. 270. 271. 272. 273. 274. 275. 276. 277. 278. 279. 280. 281. 282. 283. 284. 285. 286. 287. 288. 289. 290. 291. 292. 293. 294. 295. 296. 297. 298. 299. 300. 301. 302. 303. 304. 305. 306. 307. 308. 309. 310. 311. 312. 313. 314. 315. 316. 317. 318. 319. 320. 321. 322. 323. 324. 325. 326. 327. 328. 329. 330. 331. 332. 333. 334. 335. 336. 337. 338. 339. 340. 341. 342. 343. 344. 345. 346. 347. 348. 349. 350. 351. 352. 353. 354. 355. 356. 357. 358. 359. 360. 361. 362. 363. 364. 365. 366. 367. 368. 369. 370. 371. 372. 373. 374. 375. 376. 377. 378. 379. 380. 381. 382. 383. 384. 385. 386. 387. 388. 389. 390. 391. 392. 393. 394. 395. 396. 397. 398. 399. 400. 401. 402. 403. 404. 405. 406. 407. 408. 409. 410. 411. 412. 413. 414. 415. 416. 417. 418. 419. 420. 421. 422. 423. 424. 425. 426. 427. 428. 429. 430. 431. 432. 433. 434. 435. 436. 437. 438. 439. 440. 441. 442. 443. 444. 445. 446. 447. 448. 449. 450. 451. 452. 453. 454. 455. 456. 457. 458. 459. 460. 461. 462. 463. 464. 465. 466. 467. 468. 469. 470. 471. 472. 473. 474. 475. 476. 477. 478. 479. 480. 481. 482. 483. 484. 485. 486. 487. 488. 489. 490. 491. 492. 493. 494. 495. 496. 497. 498. 499. 500. 501. 502. 503. 504. 505. 506. 507. 508. 509. 510. 511. 512. 513. 514. 515. 516. 517. 518. 519. 520. 521. 522. 523. 524. 525. 526. 527. 528. 529. 530. 531. 532. 533. 534. 535. 536. 537. 538. 539. 540. 541. 542. 543. 544. 545. 546. 547. 548. 549. 550. 551. 552. 553. 554. 555. 556. 557. 558. 559. 560. 561. 562. 563. 564. 565. 566. 567. 568. 569. 570. 571. 572. 573. 574. 575. 576. 577. 578. 579. 580. 581. 582. 583. 584. 585. 586. 587. 588. 589. 590. 591. 592. 593. 594. 595. 596. 597. 598. 599. 600. 601. 602. 603. 604. 605. 606. 607. 608. 609. 610. 611. 612. 613. 614. 615. 616. 617. 618. 619. 620. 621. 622. 623. 624. 625. 626. 627. 628. 629. 630. 631. 632. 633. 634. 635. 636. 637. 638. 639. 640. 641. 642. 643. 644. 645. 646. 647. 648. 649. 650. 651. 652. 653. 654. 655. 656. 657. 658. 659. 660. 661. 662. 663. 664. 665. 666. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.01.2018, 19:40 |
|
||
|
|

start [/forum/topic.php?fid=58&msg=39587427&tid=2041298]: |
0ms |
get settings: |
7ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
183ms |
get topic data: |
9ms |
get forum data: |
3ms |
get page messages: |
68ms |
get tp. blocked users: |
1ms |
| others: | 203ms |
| total: | 495ms |

| 0 / 0 |
