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
 667
 668
 669
 670
 671
 672
 673
 674
 675
 676
 677
 678
 679
 680
 681
 682
 683
 684
 685
 686
 687
 688
 689
 690
 691
 692
 693
 694
 695
 696
 697
 698
 699
 700
 701
 702
 703
 704
 705
 706
 707
 708
 709
 710
 711
 712
 713
 714
 715
 716
 717
 718
 719
 720
 721
 722
 723
 724
 725
 726
 727
 728
 729
 730
 731
 732
 733
 734
 735
 736
 737
 738
 739
 740
 741
 742
 743
 744
 745
 746
 747
 748
 749
 750
 751
 752
 753
 754
 755
 756
 757
 758
 759
 760
 761
 762
 763
 764
 765
 766
 767
 768
 769
 770
 771
 772
 773
 774
 775
 776
 777
 778
 779
 780
 781
 782
 783
 784
 785
 786
 787
 788
 789
 790
 791
 792
 793
 794
 795
 796
 797
 798
 799
 800
 801
 802
 803
 804
 805
 806
 807
 808
 809
 810
 811
 812
 813
 814
 815
 816
 817
 818
 819
 820
 821
 822
 823
 824
 825
 826
 827
 828
 829
 830
 831
 832
 833
 834
 835
 836
 837
 838
 839
 840
 841
 842
 843
 844
 845
 846
 847
 848
 849
 850
 851
 852
 853
 854
 855
 856
 857
 858
 859
 860
 861
 862
 863
 864
 865
 866
 867
 868
 869
 870
 871
 872
 873
 874
 875
 876
 877
 878
 879
 880
 881
 882
 883
 884
 885
 886
 887
 888
 889
 890
 891
 892
 893
 894
 895
 896
 897
 898
 899
 900
 901
 902
 903
 904
 905
 906
 907
 908
 909
 910
 911
 912
 913
 914
 915
 916
 917
 918
 919
 920
 921
 922
 923
 924
 925
 926
 927
 928
 929
 930
 931
 932
 933
 934
 935
 936
 937
 938
 939
 940
 941
 942
 943
 944
 945
 946
 947
 948
 949
 950
 951
 952
 953
 954
 955
 956
 957
 958
 959
 960
 961
 962
 963
 964
 965
 966
 967
 968
 969
 970
 971
 972
 973
 974
 975
 976
 977
 978
 979
 980
 981
 982
 983
 984
 985
 986
 987
 988
 989
 990
 991
 992
 993
 994
 995
 996
 997
 998
 999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
2379
2380
2381
2382
2383
2384
2385
2386
2387
2388
2389
2390
2391
2392
2393
2394
2395
2396
2397
2398
2399
2400
2401
2402
2403
2404
2405
2406
2407
2408
2409
2410
2411
2412
2413
2414
2415
2416
2417
2418
2419
2420
2421
2422
2423
2424
2425
2426
2427
2428
2429
2430
2431
2432
2433
2434
2435
2436
2437
2438
2439
2440
2441
2442
2443
2444
2445
2446
2447
2448
2449
2450
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
2466
2467
2468
2469
2470
2471
2472
2473
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
2489
2490
2491
2492
2493
2494
2495
2496
2497
2498
2499
2500
2501
2502
2503
2504
2505
2506
2507
2508
2509
2510
2511
2512
2513
2514
2515
2516
2517
2518
2519
2520
2521
2522
2523
2524
2525
2526
2527
2528
2529
2530
2531
2532
2533
2534
2535
2536
2537
2538
2539
2540
2541
2542
2543
2544
2545
2546
2547
2548
2549
2550
2551
2552
2553
2554
2555
2556
2557
2558
2559
2560
2561
2562
2563
2564
2565
2566
2567
2568
2569
2570
2571
2572
2573
2574
2575
2576
2577
2578
2579
2580
2581
2582
2583
2584
2585
2586
2587
2588
2589
2590
2591
2592
2593
2594
2595
2596
2597
2598
2599
2600
2601
2602
2603
2604
2605
2606
2607
2608
2609
2610
2611
2612
2613
2614
2615
2616
2617
2618
2619
2620
2621
2622
2623
2624
2625
2626
2627
2628
2629
2630
2631
2632
2633
2634
2635
2636
2637
2638
2639
2640
2641
2642
2643
2644
2645
2646
2647
2648
2649
2650
2651
2652
2653
2654
2655
2656
2657
2658
2659
2660
2661
2662
2663
2664
2665
2666
2667
2668
2669
2670
2671
2672
2673
2674
2675
2676
2677
2678
2679
2680
2681
2682
2683
2684
2685
2686
2687
2688
2689
2690
2691
2692
2693
2694
2695
2696
2697
2698
2699
2700
2701
2702
2703
2704
2705
2706
2707
2708
2709
2710
2711
2712
2713
2714
2715
2716
2717
2718
2719
2720
2721
2722
2723
2724
2725
2726
2727
2728
2729
2730
2731
2732
2733
2734
2735
2736
2737
2738
2739
2740
2741
2742
2743
2744
2745
2746
2747
2748
2749
2750
2751
2752
2753
2754
2755
2756
2757
2758
2759
2760
2761
2762
2763
2764
2765
2766
2767
2768
2769
2770
2771
2772
2773
2774
2775
2776
2777
2778
2779
2780
2781
2782
2783
2784
2785
2786
2787
2788
2789
2790
2791
2792
2793
2794
2795
2796
2797
2798
2799
2800
2801
2802
2803
2804
2805
2806
2807
2808
2809
2810
2811
2812
2813
2814
2815
2816
2817
2818
2819
2820
2821
2822
2823
2824
2825
2826
2827
2828
2829
2830
2831
2832
2833
2834
2835
2836
2837
2838
2839
2840
2841
2842
2843
2844
2845
2846
2847
2848
2849
2850
2851
2852
2853
2854
2855
2856
2857
2858
2859
2860
2861
2862
2863
2864
2865
2866
2867
2868
2869
2870
2871
2872
2873
2874
2875
2876
2877
2878
2879
2880
2881
2882
2883
2884
2885
2886
2887
2888
2889
2890
2891
2892
2893
2894
2895
2896
2897
2898
2899
2900
2901
2902
2903
2904
2905
2906
2907
2908
2909
2910
2911
2912
2913
2914
2915
2916
2917
2918
2919
2920
2921
2922
2923
2924
2925
2926
2927
2928
2929
2930
2931
2932
2933
2934
2935
2936
2937
2938
2939
2940
2941
2942
2943
2944
2945
2946
2947
2948
2949
2950
2951
2952
2953
2954
2955
2956
2957
2958
2959
2960
2961
2962
2963
2964
2965
2966
2967
2968
2969
2970
2971
2972
2973
2974
2975
2976
2977
2978
2979
2980
2981
2982
2983
2984
2985
2986
2987
2988
2989
2990
2991
2992
2993
2994
2995
2996
2997
2998
2999
3000
3001
3002
3003
3004
3005
3006
3007
3008
3009
3010
3011
3012
3013
3014
3015
3016
3017
3018
3019
3020
3021
3022
3023
3024
3025
3026
3027
3028
3029
3030
3031
3032
3033
3034
3035
3036
3037
3038
3039
3040
3041
3042
3043
3044
3045
3046
3047
3048
3049
3050
3051
3052
3053
3054
3055
3056
3057
3058
3059
3060
3061
3062
3063
3064
3065
3066
3067
3068
3069
3070
3071
3072
3073
3074
3075
3076
3077
3078
3079
3080
3081
3082
3083
3084
3085
3086
3087
3088
3089
3090
3091
3092
3093
3094
3095
3096
3097
3098
3099
3100
3101
3102
3103
3104
3105
3106
3107
3108
3109
3110
3111
3112
3113
3114
3115
3116
3117
3118
3119
3120
3121
3122
3123
3124
3125
3126
3127
3128
3129
3130
3131
3132
3133
3134
3135
3136
3137
3138
3139
3140
3141
3142
3143
3144
3145
3146
3147
3148
3149
3150
3151
3152
3153
3154
3155
3156
3157
3158
3159
3160
3161
3162
3163
3164
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
3185
3186
3187
3188
3189
3190
3191
3192
3193
3194
3195
3196
3197
3198
3199
3200
3201
3202
3203
3204
3205
3206
3207
3208
3209
3210
3211
3212
3213
3214
3215
3216
3217
3218
3219
3220
3221
3222
3223
3224
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
3241
3242
3243
3244
3245
3246
3247
3248
3249
3250
3251
3252
3253
3254
3255
3256
3257
3258
3259
3260
3261
3262
3263
3264
3265
3266
3267
3268
3269
3270
3271
3272
3273
3274
3275
3276
3277
3278
3279
3280
3281
3282
3283
3284
3285
3286
3287
3288
3289
3290
3291
3292
3293
3294
3295
3296
3297
3298
3299
3300
3301
3302
3303
3304
3305
3306
3307
3308
3309
3310
3311
3312
3313
3314
3315
3316
3317
3318
3319
3320
3321
3322
3323
3324
3325
3326
3327
3328
3329
3330
3331
3332
3333
3334
3335
3336
3337
3338
3339
3340
3341
3342
3343
3344
3345
3346
3347
3348
3349
3350
3351
3352
3353
3354
3355
3356
3357
3358
3359
3360
3361
3362
3363
3364
3365
3366
3367
3368
3369
3370
3371
3372
3373
3374
3375
3376
3377
3378
3379
3380
3381
3382
3383
3384
3385
3386
3387
3388
3389
3390
3391
3392
3393
3394
3395
3396
3397
3398
3399
3400
3401
3402
3403
3404
3405
3406
3407
3408
3409
3410
3411
3412
3413
3414
3415
3416
3417
3418
3419
3420
3421
3422
3423
3424
3425
3426
3427
3428
3429
3430
3431
3432
3433
3434
3435
3436
3437
3438
3439
3440
3441
3442
3443
3444
3445
3446
3447
3448
3449
3450
3451
3452
3453
3454
3455
3456
3457
3458
3459
3460
3461
3462
3463
3464
3465
3466
3467
3468
3469
3470
3471
3472
3473
3474
3475
3476
3477
3478
3479
3480
3481
3482
3483
3484
3485
3486
3487
3488
3489
3490
3491
3492
3493
3494
3495
3496
3497
3498
3499
3500
3501
3502
3503
3504
3505
3506
3507
3508
3509
3510
3511
3512
3513
3514
3515
3516
3517
3518
3519
3520
3521
3522
3523
3524
3525
3526
3527
3528
3529
3530
3531
3532
3533
3534
3535
3536
3537
3538
3539
3540
3541
3542
3543
3544
3545
3546
3547
3548
3549
3550
3551
3552
3553
3554
3555
3556
3557
3558
3559
3560
3561
3562
3563
3564
3565
3566
3567
3568
3569
3570
3571
3572
3573
3574
3575
3576
3577
3578
3579
3580
3581
3582
3583
3584
3585
3586
3587
3588
3589
3590
3591
3592
3593
3594
3595
3596
3597
3598
3599
3600
3601
3602
3603
3604
3605
3606
3607
3608
3609
3610
3611
3612
3613
3614
3615
3616
3617
3618
3619
3620
3621
3622
3623
3624
3625
3626
3627
3628
3629
3630
3631
3632
3633
3634
3635
3636
3637
3638
3639
3640
3641
3642
3643
3644
3645
3646
3647
3648
3649
3650
3651
3652
3653
3654
3655
3656
3657
3658
3659
3660
3661
3662
3663
3664
3665
3666
3667
3668
3669
3670
3671
3672
3673
3674
3675
3676
3677
3678
3679
3680
3681
3682
3683
3684
3685
3686
3687
3688
3689
3690
3691
3692
3693
3694
3695
3696
3697
3698
3699
3700
3701
3702
3703
3704
3705
3706
3707
3708
3709
3710
3711
3712
3713
3714
3715
3716
3717
3718
3719
3720
3721
3722
3723
3724
3725
3726
3727
3728
3729
3730
3731
3732
3733
3734
3735
3736
3737
3738
3739
3740
3741
3742
3743
3744
3745
3746
3747
3748
3749
3750
3751
3752
3753
3754
3755
3756
3757
3758
3759
3760
3761
3762
3763
3764
3765
3766
3767
3768
3769
3770
3771
3772
3773
3774
3775
3776
3777
3778
3779
3780
3781
3782
3783
3784
3785
3786
3787
3788
3789
3790
3791
3792
3793
3794
3795
3796
3797
3798
3799
3800
3801
3802
3803
3804
3805
3806
3807
3808
3809
3810
3811
3812
3813
3814
3815
3816
3817
3818
3819
3820
3821
3822
3823
3824
3825
3826
3827
3828
3829
3830
3831
3832
3833
3834
3835
3836
3837
3838
3839
3840
3841
3842
3843
3844
3845
3846
3847
3848
3849
3850
3851
3852
3853
3854
3855
3856
3857
3858
3859
3860
3861
3862
3863
3864
3865
3866
3867
3868
3869
3870
3871
3872
3873
3874
3875
3876
3877
3878
3879
3880
3881
3882
3883
3884
3885
3886
3887
3888
3889
3890
3891
3892
3893
3894
3895
3896
3897
3898
3899
3900
3901
3902
3903
3904
3905
3906
3907
3908
3909
3910
3911
3912
3913
3914
3915
3916
3917
3918
3919
3920
3921
3922
3923
3924
3925
3926
3927
3928
3929
3930
3931
3932
3933
3934
3935
3936
3937
3938
3939
3940
3941
3942
3943
3944
3945
3946
3947
3948
3949
3950
3951
3952
3953
3954
3955
3956
3957
3958
3959
3960
3961
3962
3963
3964
3965
3966
3967
3968
3969
3970
3971
3972
3973
3974
3975
3976
3977
3978
3979
3980
3981
3982
3983
3984
3985
3986
3987
3988
3989
3990
3991
3992
3993
3994
3995
3996
3997
3998
3999
4000
4001
4002
4003
4004
4005
4006
4007
4008
4009
4010
4011
4012
4013
4014
4015
4016
4017
4018
4019
4020
4021
4022
4023
4024
4025
4026
4027
4028
4029
4030
4031
4032
4033
4034
4035
4036
4037
4038
4039
4040
4041
1
00:00:00,000 --> 00:00:00,500

2
00:00:00,500 --> 00:00:03,340
[Музика свири]

3
00:00:03,340 --> 00:00:11,020

4
00:00:11,020 --> 00:00:14,010
>> DAVID Маланом: Ова е CS50.

5
00:00:14,010 --> 00:00:18,090
И ова е како на почетокот и
end-- како literally-- речиси на крајот

6
00:00:18,090 --> 00:00:18,825
на шест неделно.

7
00:00:18,825 --> 00:00:20,030

8
00:00:20,030 --> 00:00:22,640
>> Мислев дека ќе го споделам
малку забава факт.

9
00:00:22,640 --> 00:00:25,370
Сум се повлече на овој горе од
податоци минатото семестар во собата.

10
00:00:25,370 --> 00:00:29,710
Може да се потсетиме дека бараме од вас на секој
стр сет форма, ако си гледал онлајн

11
00:00:29,710 --> 00:00:31,580
или ако сте присуствуваше лично.

12
00:00:31,580 --> 00:00:33,020
И тука е на податоци.

13
00:00:33,020 --> 00:00:34,710
Така, денес е многу предвидлива.

14
00:00:34,710 --> 00:00:37,126
Но сакавме да потрошите малку
на време со вас сеедно.

15
00:00:37,126 --> 00:00:40,599
Некој би сакал да се нагаѓа зошто ова
графикон е толку JAGGY, нагоре надолу, нагоре надолу,

16
00:00:40,599 --> 00:00:41,265
така постојано?

17
00:00:41,265 --> 00:00:42,980

18
00:00:42,980 --> 00:00:45,130
Што прават секој од врвови
и корита претставуваат?

19
00:00:45,130 --> 00:00:46,005
>> ПУБЛИКАТА: [нечујни]

20
00:00:46,005 --> 00:00:47,002

21
00:00:47,002 --> 00:00:47,835
DAVID Маланом: Навистина.

22
00:00:47,835 --> 00:00:50,900

23
00:00:50,900 --> 00:00:55,480
И повеќе интересно, не дај Боже,
ние се одржи едно предавање во петок

24
00:00:55,480 --> 00:00:58,960
на почетокот на семестарот,
тоа е она што го гледаме се случи.

25
00:00:58,960 --> 00:01:03,430
Така, денес, ние се причестуваат во малку
повеќе за структури на податоци.

26
00:01:03,430 --> 00:01:06,660
И да ви даде повеќе од солидна
ментална модел за проблемите во пет,

27
00:01:06,660 --> 00:01:07,450
кој е сега надвор.

28
00:01:07,450 --> 00:01:10,817
Правописни грешки, при што, ние ќе
ви рака текстуална датотека околу 100.000

29
00:01:10,817 --> 00:01:12,650
плус Английский зборови, и
ви се случува да имаат

30
00:01:12,650 --> 00:01:17,770
да дознаам како да умно ги вчитате
во меморијата, во RAM меморија, користејќи некои податоци

31
00:01:17,770 --> 00:01:19,330
структурата на вашиот избор.

32
00:01:19,330 --> 00:01:22,470
>> Веднаш еден таков податоци структура може да
да биде, но веројатно не треба да биде,

33
00:01:22,470 --> 00:01:25,630
прилично симплистички поврзана листа,
кои воведовме минатиот пат.

34
00:01:25,630 --> 00:01:29,220
И поврзана листа имале барем
едно предност во однос на низа.

35
00:01:29,220 --> 00:01:32,096
Што е една предност на
поврзана листа веројатно?

36
00:01:32,096 --> 00:01:32,950
>> ПУБЛИКАТА: вметнување.

37
00:01:32,950 --> 00:01:33,908
>> DAVID Маланом: вметнување.

38
00:01:33,908 --> 00:01:34,155

39
00:01:34,155 --> 00:01:35,196
Што сакаш да кажеш со тоа?

40
00:01:35,196 --> 00:01:37,872
>> ПУБЛИКАТА: Насекаде заедно
Листа [нечујни].

41
00:01:37,872 --> 00:01:38,770
>> DAVID Маланом: Добро.

42
00:01:38,770 --> 00:01:42,090
Така можете да вметнете елемент секаде каде
сакате во средината на листата

43
00:01:42,090 --> 00:01:45,490
без да се влага ништо,
кои заклучивме, во нашата сортирање

44
00:01:45,490 --> 00:01:47,630
дискусии, не е
секогаш добра работа,

45
00:01:47,630 --> 00:01:51,200
бидејќи е потребно време за да всушност се движат
сите оние луѓе лево или десно.

46
00:01:51,200 --> 00:01:55,540
И така со поврзана листа, можете да
само ги распредели со Примерок, нов јазол,

47
00:01:55,540 --> 00:01:58,385
а потоа и ажурирање на неколку
pointers-- два, три операции max--

48
00:01:58,385 --> 00:02:01,480
и ние сме во можност да слот некој
во било каде во листа.

49
00:02:01,480 --> 00:02:03,550
>> Што друго е поволна
околу поврзана листа?

50
00:02:03,550 --> 00:02:04,980

51
00:02:04,980 --> 00:02:05,659
Да?

52
00:02:05,659 --> 00:02:06,534
>> ПУБЛИКАТА: [нечујни]

53
00:02:06,534 --> 00:02:07,538

54
00:02:07,538 --> 00:02:08,413
DAVID Маланом: Совршена.

55
00:02:08,413 --> 00:02:10,590

56
00:02:10,590 --> 00:02:11,090
Совршен.

57
00:02:11,090 --> 00:02:12,070
Тоа е навистина динамичен.

58
00:02:12,070 --> 00:02:15,100
И дека не сте извршиле,
во однапред, за да некои фиксна големина на

59
00:02:15,100 --> 00:02:18,750
парче на меморија, како што ќе има
до со низа, главата, од кои

60
00:02:18,750 --> 00:02:22,455
е тоа што ќе може да одвои јазли само на
барање на тој начин со користење на само колку простор

61
00:02:22,455 --> 00:02:23,330
како што всушност треба.

62
00:02:23,330 --> 00:02:26,830
За разлика низа, може да
случајно се доделат премалку.

63
00:02:26,830 --> 00:02:28,871
И тогаш тоа е само ќе
за да биде болка во вратот

64
00:02:28,871 --> 00:02:32,440
да ги пренамени нови поголеми низа, копирајте
сè што повеќе, ослободи стариот низа,

65
00:02:32,440 --> 00:02:33,990
а потоа се движи вашиот бизнис.

66
00:02:33,990 --> 00:02:37,479
Или уште полошо, може да се доделат начин
повеќе меморија отколку што навистина треба,

67
00:02:37,479 --> 00:02:40,520
и така си оди за да имаат многу
слабо населени низа, така да се каже.

68
00:02:40,520 --> 00:02:44,350
>> Така поврзана листа дава овие
Предностите на динамичност и флексибилност

69
00:02:44,350 --> 00:02:46,080
со инсерции и бришење.

70
00:02:46,080 --> 00:02:48,000
Но сигурно мора да има цена платена.

71
00:02:48,000 --> 00:02:50,000
Всушност, една од темите
проучени квиз нула

72
00:02:50,000 --> 00:02:52,430
беше неколку размени
ние сме виделе досега.

73
00:02:52,430 --> 00:02:56,161
Значи она што е платена цена или
Недостатоци на поврзани листа?

74
00:02:56,161 --> 00:02:56,660
Да.

75
00:02:56,660 --> 00:02:57,560
>> ПУБЛИКАТА: Не случаен пристап.

76
00:02:57,560 --> 00:02:58,809
>> DAVID Маланом: Не случаен пристап.

77
00:02:58,809 --> 00:02:59,540
Но кој се грижи?

78
00:02:59,540 --> 00:03:01,546
Случаен пристап не звучи релевантни.

79
00:03:01,546 --> 00:03:02,421
>> ПУБЛИКАТА: [нечујни]

80
00:03:02,421 --> 00:03:04,865

81
00:03:04,865 --> 00:03:05,740
DAVID Маланом: Токму така.

82
00:03:05,740 --> 00:03:07,580
Ако сакате да имате
одредени algorithm--

83
00:03:07,580 --> 00:03:10,170
и дозволете ми да всушност предложи
бинарен пребарување особено, кои

84
00:03:10,170 --> 00:03:12,600
е еден ние сме се користи доста bit--
ако немате случаен пристап,

85
00:03:12,600 --> 00:03:15,516
не можете да го направите тоа едноставни аритметички
на изнаоѓање како средината елемент

86
00:03:15,516 --> 00:03:16,530
и скокање право на него.

87
00:03:16,530 --> 00:03:20,239
Вие наместо треба да почне во првата
елемент и линеарно пребарување од лево

88
00:03:20,239 --> 00:03:22,780
кон десно, ако сакате да се најде
средината или било кој друг елемент.

89
00:03:22,780 --> 00:03:24,410
>> ПУБЛИКАТА: Тоа веројатно е потребно повеќе меморија.

90
00:03:24,410 --> 00:03:25,040
>> DAVID Маланом: требаат повеќе меморија.

91
00:03:25,040 --> 00:03:27,464
Каде е дека дополнителни
чини доаѓаат од во меморијата?

92
00:03:27,464 --> 00:03:28,339
>> ПУБЛИКАТА: [нечујни]

93
00:03:28,339 --> 00:03:32,566

94
00:03:32,566 --> 00:03:33,440
DAVID Маланом: Токму така.

95
00:03:33,440 --> 00:03:35,679
Во овој случај тука, имавме
поврзана листа за цели броеви,

96
00:03:35,679 --> 00:03:37,470
а сепак ние сме удвојување
количината на меморија

97
00:03:37,470 --> 00:03:39,680
ние треба, исто така, од страна на чување на овие совети.

98
00:03:39,680 --> 00:03:42,090
Сега е помалку од една голема зделка, како
Вашата structs се поголеми

99
00:03:42,090 --> 00:03:45,320
и сте чување не е број, но
можеби студент или некој друг објект.

100
00:03:45,320 --> 00:03:46,880
Но поентата сигурно останува.

101
00:03:46,880 --> 00:03:49,421
И толку голем број на операции
на поврзани листи биле повикани

102
00:03:49,421 --> 00:03:50,570
беа големи О на N-- линеарна.

103
00:03:50,570 --> 00:03:54,730
Работи како вметнување или пребарување
или бришење во случај на елемент

104
00:03:54,730 --> 00:03:57,720
се случи да биде на самиот крај на
листата без разлика дали е подредени или не.

105
00:03:57,720 --> 00:04:01,167
>> Понекогаш можеби ќе имаат среќа и во
така пониски граници на овие операции

106
00:04:01,167 --> 00:04:04,250
исто така може да биде константна време ако сте
секогаш се гледа во првиот елемент,

107
00:04:04,250 --> 00:04:05,070
на пример.

108
00:04:05,070 --> 00:04:09,360
Но на крајот, ние вети
за да се постигне светиот грал

109
00:04:09,360 --> 00:04:12,630
на структури на податоци, или
некои обновувањето од него, како

110
00:04:12,630 --> 00:04:14,290
по пат на постојана време.

111
00:04:14,290 --> 00:04:17,579
Можеме да најдеме елементи или да додадете елементи
или отстраните елементи од листата?

112
00:04:17,579 --> 00:04:19,059
Ние ќе видиме доста наскоро.

113
00:04:19,059 --> 00:04:21,100
И излегува дека еден
на механизмите сме

114
00:04:21,100 --> 00:04:23,464
случува да започне да се користи и денес,
годишна употреба во стр постави пет,

115
00:04:23,464 --> 00:04:24,630
е всушност прилично познато.

116
00:04:24,630 --> 00:04:27,430
На пример, ако тоа е еден куп
на испит книги, од кои секоја

117
00:04:27,430 --> 00:04:29,660
има студентот прв
име и презиме на неа,

118
00:04:29,660 --> 00:04:31,820
и јас ги собереш од
на крајот на испит,

119
00:04:31,820 --> 00:04:33,746
и сите тие се доста
многу во случаен редослед,

120
00:04:33,746 --> 00:04:36,370
и ние сакаме да се обратите за сортирање
овие испити, така што еднаш оценето

121
00:04:36,370 --> 00:04:38,661
тоа е само многу полесно и
побрзо да ги предаде назад

122
00:04:38,661 --> 00:04:40,030
на студентите по азбучен ред.

123
00:04:40,030 --> 00:04:42,770
Она што ќе биде вашиот инстинкти
за еден куп на испити, како тоа?

124
00:04:42,770 --> 00:04:45,019
>> Па, ако сте како мене, ти
може да се види дека ова е m,

125
00:04:45,019 --> 00:04:48,505
па јас ќе одам да се вид на се стави ова во,
ако ова е мојата маса или ми кат каде

126
00:04:48,505 --> 00:04:50,650
Јас сум ширење работи
out-- или мојот низа really--

127
00:04:50,650 --> 00:04:52,210
Јас би можеле да се стави сите на г-ѓа таму.

128
00:04:52,210 --> 00:04:52,710
Ох.

129
00:04:52,710 --> 00:04:55,020
Еве А. Па јас би можеле да
стави Како овде.

130
00:04:55,020 --> 00:04:55,520
Ох.

131
00:04:55,520 --> 00:04:57,980
Еве уште еден А. Одам
да се стави дека овде.

132
00:04:57,980 --> 00:05:02,490
Еве З. Еве уште еден М. И така
Јас би можеле да почнат да прават купови вака.

133
00:05:02,490 --> 00:05:06,620
А потоа можеби и јас ќе одам во подоцнежните
и вид на многу nitpicky-ly вид

134
00:05:06,620 --> 00:05:07,710
поединецот хемороиди.

135
00:05:07,710 --> 00:05:11,300
Но поентата е јас ќе изгледа
на внесување на што сум раце

136
00:05:11,300 --> 00:05:14,016
и јас ќе го направи некои пресметува
одлука врз основа на кој влез.

137
00:05:14,016 --> 00:05:15,640
Ако тоа започнува со, го стави таму.

138
00:05:15,640 --> 00:05:18,980
Ако тоа започнува со Z, го стави над
таму, и сето она помеѓу.

139
00:05:18,980 --> 00:05:22,730
>> Па ова е техника која е
општо позната како hashing-- H-A-S-Н-

140
00:05:22,730 --> 00:05:26,550
кои обично значи дека земајќи ја како
влезни и користење на тоа влез за да се пресмета

141
00:05:26,550 --> 00:05:30,940
вредност, обично голем број, и дека
број е индекс во складирање

142
00:05:30,940 --> 00:05:32,260
сад, како низа.

143
00:05:32,260 --> 00:05:35,490
Значи со други зборови, јас би можеле да имаат
хеш функција, како што правам јас во мојата глава,

144
00:05:35,490 --> 00:05:37,940
дека ако видам некој е
име кој започнува со,

145
00:05:37,940 --> 00:05:40,190
Одам да се мапираат дека
на нула во мојата глава.

146
00:05:40,190 --> 00:05:44,160
И ако видам некој со Z, јас сум
се случува да се на сајтот, кој до 25 во мојата глава

147
00:05:44,160 --> 00:05:46,220
а потоа се стави дека во
последните повеќето куп.

148
00:05:46,220 --> 00:05:50,990
>> Сега, ако мислите дека за не мојот мозок
но C програма, што броеви може да

149
00:05:50,990 --> 00:05:53,170
ви се потпрат за да се постигне тоа истиот резултат?

150
00:05:53,170 --> 00:05:55,594
Со други зборови, ако се
имаше ASCII карактер,

151
00:05:55,594 --> 00:05:57,510
како да се утврди
она кофа да го стави во?

152
00:05:57,510 --> 00:05:59,801
Најверојатно не сакаат да
стави ја во кофа 65, која

153
00:05:59,801 --> 00:06:01,840
ќе биде како таму
без добра причина.

154
00:06:01,840 --> 00:06:04,320
Каде сакате да се стави
во однос на нејзината ASCII вредност?

155
00:06:04,320 --> 00:06:05,600

156
00:06:05,600 --> 00:06:08,920
Каде сакате да направите за да нејзините ASCII
вредност да излезе со попаметни кофа

157
00:06:08,920 --> 00:06:09,480
да го стави во?

158
00:06:09,480 --> 00:06:10,206
>> ПУБЛИКАТА: Минус А.

159
00:06:10,206 --> 00:06:10,956
>> DAVID Маланом: Да.

160
00:06:10,956 --> 00:06:13,190
Па минус А или минус
конкретно 65, ако тоа е

161
00:06:13,190 --> 00:06:18,240
капитал А. Или 98, ако
тоа е со мали букви.

162
00:06:18,240 --> 00:06:21,300
И, така што ќе ни овозможи да се, многу
едноставно и многу аритметички,

163
00:06:21,300 --> 00:06:23,260
стави нешто во кофа како тоа.

164
00:06:23,260 --> 00:06:26,010
Така што се испоставува, ние всушност го направите
оваа, како и дури и со квизови.

165
00:06:26,010 --> 00:06:29,051
>> Па можеби ќе се сетат ли заокружено вашиот
име настава колеги е на насловната страница.

166
00:06:29,051 --> 00:06:32,270
И беа организирани имиња ТФ
во овие колумни по азбучен ред,

167
00:06:32,270 --> 00:06:34,400
и, верувале или не,
кога сите 80 плус од нас

168
00:06:34,400 --> 00:06:37,800
здруживме друга ноќ да одделение,
Последниот чекор во нашата оценување процес

169
00:06:37,800 --> 00:06:41,830
е да хаш на тестови во голем
простор на подот на [нечујни]

170
00:06:41,830 --> 00:06:45,110
и да се постават квизови сите надвор
во точно редоследот на нивната ТФ

171
00:06:45,110 --> 00:06:47,700
имиња на насловната страница, бидејќи
тогаш тоа е многу полесно за нас

172
00:06:47,700 --> 00:06:51,290
да се бара преку дека за користење на линеарна
пребарување или некој вид на мудрост

173
00:06:51,290 --> 00:06:54,050
за ТФ да се најдат неговите или
квизови нејзините ученици.

174
00:06:54,050 --> 00:06:56,060
>> Па оваа идеја на hashing
тоа ќе го видите е

175
00:06:56,060 --> 00:07:00,520
доста моќен е всушност прилично
вообичаена и многу интуитивен,

176
00:07:00,520 --> 00:07:03,000
многу како можеби се делат и
Conquer беше во недела нула.

177
00:07:03,000 --> 00:07:05,250
Јас брзо напред до Hackathon
пред неколку години.

178
00:07:05,250 --> 00:07:08,040
Оваа беше Zamyla и неколку
други вработени поздрав студенти

179
00:07:08,040 --> 00:07:09,030
како што дојде во.

180
00:07:09,030 --> 00:07:12,680
И имавме куп преклопен
табели таму со имињата.

181
00:07:12,680 --> 00:07:15,380
И имавме имињата на организиран
со слични Како што таму

182
00:07:15,380 --> 00:07:16,690
и З.Ш. таму.

183
00:07:16,690 --> 00:07:20,350
И така еден од TFS многу умно
напиша на ова како на инструкции

184
00:07:20,350 --> 00:07:21,030
за тој ден.

185
00:07:21,030 --> 00:07:24,480
И во 12 недела од семестарот ова
сите направени совршена смисла и сите

186
00:07:24,480 --> 00:07:25,310
знаеше што да прави.

187
00:07:25,310 --> 00:07:27,900
Но во секое време сте
подредени во ист начин,

188
00:07:27,900 --> 00:07:30,272
сте за спроведување на
истиот поим на хашиш.

189
00:07:30,272 --> 00:07:31,730
Така нека си го малку формализира.

190
00:07:31,730 --> 00:07:32,890
Тука е низа.

191
00:07:32,890 --> 00:07:36,820
Се подготвени да биде малку
широк само да ги отслика, визуелно,

192
00:07:36,820 --> 00:07:38,920
дека ние може да се стави жици
во нешто како ова.

193
00:07:38,920 --> 00:07:41,970
И оваа низа е
јасно на вкупната големина 26.

194
00:07:41,970 --> 00:07:43,935
И нешто што се нарекува
маса произволно.

195
00:07:43,935 --> 00:07:48,930
Но, ова е само препевот на уметникот
на она што хаш табелата може да биде.

196
00:07:48,930 --> 00:07:52,799
>> Така хаш табелата сега се случува да
биде на повисоко ниво на податоци структура.

197
00:07:52,799 --> 00:07:54,840
На крајот на денот
ние сме за да се види дека

198
00:07:54,840 --> 00:07:58,700
може да се спроведе хаш табелата, која
е многу сличен на проверка во линија

199
00:07:58,700 --> 00:08:02,059
на Hackathon многу вака
маса се користат за подредување испит книги.

200
00:08:02,059 --> 00:08:03,850
Но хаш табелата е
вид на ова високо ниво

201
00:08:03,850 --> 00:08:08,250
концепт кој би можел да користи низа
под хаубата да ја спроведат,

202
00:08:08,250 --> 00:08:11,890
или пак може да се користи листата должина, или дури и
можеби некои други структури на податоци.

203
00:08:11,890 --> 00:08:15,590
И сега тоа е theme-- преземање
некои од овие основни состојки

204
00:08:15,590 --> 00:08:18,310
како низа и оваа зграда
блокира сега на листа должина

205
00:08:18,310 --> 00:08:21,740
и види што друго можеме да изградиме
на врвот на оние, како состојки

206
00:08:21,740 --> 00:08:26,550
во рецепт, со што се повеќе и повеќе
интересни и корисни конечните резултати.

207
00:08:26,550 --> 00:08:28,680
>> Па со хаш табелата
да ја спроведе

208
00:08:28,680 --> 00:08:32,540
во меморијата сликовито вака, но
како може тоа всушност се кодира нагоре?

209
00:08:32,540 --> 00:08:33,789
Па, можеби едноставно како е ова.

210
00:08:33,789 --> 00:08:38,270
Ако капацитет во сите капи, е само
некои constant-- на пример 26,

211
00:08:38,270 --> 00:08:42,030
за 26 писма на alphabet--
Јас би можеле да се јавам на моите променлива маса,

212
00:08:42,030 --> 00:08:45,630
и јас би можеле да тврдат дека јас ќе одам да
стави знак ѕвезди во таму, или стринг.

213
00:08:45,630 --> 00:08:49,880
Така, тоа е толку едноставно како ова ако
сакате да се спроведе хаш табелата.

214
00:08:49,880 --> 00:08:51,490
А сепак, ова е навистина само низа.

215
00:08:51,490 --> 00:08:53,198
Но, повторно, хаш
маса е сега што ние ќе

216
00:08:53,198 --> 00:08:57,470
јавете се апстрактни тип на податоци, тоа е само
вид на концептуална наслояване на врвот

217
00:08:57,470 --> 00:09:00,780
на нешто повеќе светски
сега како низа.

218
00:09:00,780 --> 00:09:02,960
>> Сега, како да одиме
за решавање на проблемите?

219
00:09:02,960 --> 00:09:06,980
Па, порано имав луксуз
имаат доволно маса простор тука

220
00:09:06,980 --> 00:09:09,460
така што би можел да стави
квизови насекаде сакав.

221
00:09:09,460 --> 00:09:10,620
Па како може да оди тука.

222
00:09:10,620 --> 00:09:12,100
ZS може да оди тука.

223
00:09:12,100 --> 00:09:13,230
Г-ѓа може да оди тука.

224
00:09:13,230 --> 00:09:14,740
А потоа имав некои екстра простор.

225
00:09:14,740 --> 00:09:18,740
Но, ова е малку измамник право
сега, бидејќи оваа табела, ако јас навистина

226
00:09:18,740 --> 00:09:22,720
мислев на тоа како низа, е само
ќе биде на некоја фиксна големина.

227
00:09:22,720 --> 00:09:25,380
>> Па технички, ако јас се повлече
до квиз друг ученик

228
00:09:25,380 --> 00:09:28,490
и да видиме, ох, овој човек
име започнува со премногу,

229
00:09:28,490 --> 00:09:30,980
Јас вид на сакаат да го стави таму.

230
00:09:30,980 --> 00:09:34,740
Но, штом го ставив таму, ако
оваа табела навистина претставува низа,

231
00:09:34,740 --> 00:09:37,840
Одам да се императивни или затирания
кој и квиз овој ученик е.

232
00:09:37,840 --> 00:09:38,340
Нели?

233
00:09:38,340 --> 00:09:41,972
Ако ова е низа, само едно нешто може да
оди во секоја од овие клетки или елементи.

234
00:09:41,972 --> 00:09:43,680
И така јас вид на имаат
да одбереш.

235
00:09:43,680 --> 00:09:45,735
>> Сега порано јас вид на
измамени и го направи ова или јас

236
00:09:45,735 --> 00:09:47,526
само вид на рангирани
им горе едни со други.

237
00:09:47,526 --> 00:09:49,170
Но, тоа не се случува да лета во кодот.

238
00:09:49,170 --> 00:09:52,260
Значи, каде што би можеле да го ставам
втор студент чие име

239
00:09:52,260 --> 00:09:54,964
е ако сите морав е ова
достапни маса простор?

240
00:09:54,964 --> 00:09:57,880
И јас сум користел три слота и тоа
изгледа како таму е само уште неколку други.

241
00:09:57,880 --> 00:09:58,959
Она што можете да направите?

242
00:09:58,959 --> 00:09:59,834
ПУБЛИКАТА: [нечујни]

243
00:09:59,834 --> 00:10:00,565

244
00:10:00,565 --> 00:10:01,315
DAVID Маланом: Да.

245
00:10:01,315 --> 00:10:02,370
Можеби ајде да го прости.

246
00:10:02,370 --> 00:10:02,660
Нели?

247
00:10:02,660 --> 00:10:04,243
Тоа не се вклопува каде што сакам да го стави.

248
00:10:04,243 --> 00:10:07,450
Па ќе одам да го стави
технички каде Б ќе одат.

249
00:10:07,450 --> 00:10:09,932
Момент, се разбира, јас сум почнуваат
да си ја наслика во еден агол.

250
00:10:09,932 --> 00:10:11,890
Ако стигнам до студент
чие име е всушност Б,

251
00:10:11,890 --> 00:10:14,840
сега B се случува да бидат преместени малку
напред, како што може да се случи, да,

252
00:10:14,840 --> 00:10:17,530
ако ова е Б, сега мора да оди тука.

253
00:10:17,530 --> 00:10:20,180
>> Па така ова многу брзо
може да стане проблематично,

254
00:10:20,180 --> 00:10:23,850
но тоа е техника која, всушност,
е наведен како линеарна љубопитство,

255
00:10:23,850 --> 00:10:26,650
со која само се разгледа вашата
низа да биде должината на линијата.

256
00:10:26,650 --> 00:10:29,680
А вие само вид на сондата или
увид секој елемент достапни

257
00:10:29,680 --> 00:10:31,360
во потрага по достапни на самото место.

258
00:10:31,360 --> 00:10:34,010
И веднаш штом ќе се најде
еден, го откажа во таму.

259
00:10:34,010 --> 00:10:38,390
>> Сега, цената се плаќа сега
за овој раствор е што?

260
00:10:38,390 --> 00:10:41,300
Имаме фиксна големина на низата,
и кога јас вметнете имиња

261
00:10:41,300 --> 00:10:44,059
во него, барем на почетокот, што е
трчање време на вметнување

262
00:10:44,059 --> 00:10:46,350
за ставање на студентите
квизови во право кофи?

263
00:10:46,350 --> 00:10:48,710

264
00:10:48,710 --> 00:10:50,002
Биг О на што?

265
00:10:50,002 --> 00:10:51,147
>> ПУБЛИКАТА: n.

266
00:10:51,147 --> 00:10:52,480
DAVID Маланом: Еднаш го слушнав голема О на n.

267
00:10:52,480 --> 00:10:53,530

268
00:10:53,530 --> 00:10:54,300
Не е точно.

269
00:10:54,300 --> 00:10:56,490
Но ние ќе ги разграничат
зошто во само еден миг.

270
00:10:56,490 --> 00:10:57,702
Што друго може да е?

271
00:10:57,702 --> 00:10:58,755
>> ПУБЛИКАТА: [нечујни]

272
00:10:58,755 --> 00:11:00,380
DAVID Маланом: И дозволете ми да го направи визуелно.

273
00:11:00,380 --> 00:11:04,720
Така да претпоставиме ова е писмо С.

274
00:11:04,720 --> 00:11:05,604
>> ПУБЛИКАТА: Тоа е една.

275
00:11:05,604 --> 00:11:06,520
DAVID Маланом: Тоа е една.

276
00:11:06,520 --> 00:11:06,710
Нели?

277
00:11:06,710 --> 00:11:08,950
Оваа е низа, која
значи имаме случаен пристап.

278
00:11:08,950 --> 00:11:11,790
И ако мислиме на ова
како нула и ова како 25,

279
00:11:11,790 --> 00:11:13,800
и сфаќаме дека,
ох, тука е мојот влез С,

280
00:11:13,800 --> 00:11:16,350
Јас секако може да се конвертира
S, ASCII карактер,

281
00:11:16,350 --> 00:11:18,540
до соодветен број
помеѓу нула и 25

282
00:11:18,540 --> 00:11:20,910
и потоа веднаш
стави го таму каде што припаѓа.

283
00:11:20,910 --> 00:11:26,120
>> Но, се разбира, штом стигнам до
вториот човек кој е име е А или Б или Ц

284
00:11:26,120 --> 00:11:29,300
на крајот, ако јас сум користел
линеарни љубопитство како моето решение,

285
00:11:29,300 --> 00:11:31,360
трчање време на
вметнување во најлош случај

286
00:11:31,360 --> 00:11:33,120
е всушност ќе се префрлат во што?

287
00:11:33,120 --> 00:11:34,270

288
00:11:34,270 --> 00:11:36,045
И јас го чувам тука
правилно рано.

289
00:11:36,045 --> 00:11:36,920
ПУБЛИКАТА: [нечујни]

290
00:11:36,920 --> 00:11:41,620
DAVID Маланом: Значи тоа е n навистина еднаш
имате доволно голема група на податоци.

291
00:11:41,620 --> 00:11:44,410
Па, од една страна, ако
Вашата низа е доволно голем

292
00:11:44,410 --> 00:11:48,287
и на вашите податоци е редок доволно,
добие оваа прекрасна константно време.

293
00:11:48,287 --> 00:11:50,620
Но штом ќе почнете да
добивање на повеќе и повеќе елементи,

294
00:11:50,620 --> 00:11:53,200
и само статистички ќе добиете
повеќе луѓе со писмо

295
00:11:53,200 --> 00:11:56,030
Како и нивните име или писмо
B, тоа може потенцијално

296
00:11:56,030 --> 00:11:57,900
префрлат во нешто повеќе линеарна.

297
00:11:57,900 --> 00:11:59,640
Па не е сосема совршена.

298
00:11:59,640 --> 00:12:00,690
Така би можеле да го направи подобро?

299
00:12:00,690 --> 00:12:03,210
>> Па, што беше наша
решение пред кога ние

300
00:12:03,210 --> 00:12:06,820
сакаат да имаат повеќе динамика од
нешто како низа дозволено?

301
00:12:06,820 --> 00:12:08,085

302
00:12:08,085 --> 00:12:08,960
ПУБЛИКАТА: [нечујни]

303
00:12:08,960 --> 00:12:10,030
DAVID Маланом: Што ќе се воведат?

304
00:12:10,030 --> 00:12:10,530
Да.

305
00:12:10,530 --> 00:12:11,430
Така поврзана листа.

306
00:12:11,430 --> 00:12:14,430
Па, ајде да видиме што се поврзани
Списокот може да направи за нас наместо тоа.

307
00:12:14,430 --> 00:12:17,630
Па, дозволете ми да предложи дека ние
подготви слика како што следи.

308
00:12:17,630 --> 00:12:19,620
Сега ова е различен
слика од примерот

309
00:12:19,620 --> 00:12:24,750
од различен текст, всушност, дека
е, всушност, користејќи низа на големина 31.

310
00:12:24,750 --> 00:12:28,220
И овој автор едноставно
одлучи да најде жици

311
00:12:28,220 --> 00:12:32,430
не врз основа на имиња на лицето,
но врз основа на нивните birthdates.

312
00:12:32,430 --> 00:12:35,680
Без оглед на месец, тие сфатиле
ако сте родени на првиот од еден месец

313
00:12:35,680 --> 00:12:39,580
или 31 месец, авторот
ќе хаш врз основа на таа вредност,

314
00:12:39,580 --> 00:12:44,154
па како да се шири на имиња од малку
повеќе од само 26 точки може да им овозможи на.

315
00:12:44,154 --> 00:12:47,320
И можеби тоа е малку повеќе униформа
отколку да се оди со азбучен букви,

316
00:12:47,320 --> 00:12:50,236
бидејќи секако има веројатно
повеќе луѓе во светот со имиња

317
00:12:50,236 --> 00:12:54,020
дека проектот со од сигурно
некои други букви од азбуката.

318
00:12:54,020 --> 00:12:56,380
Па можеби ова е малку
повеќе униформа, под претпоставка

319
00:12:56,380 --> 00:12:58,640
еднообразна дистрибуција
на бебиња низ еден месец.

320
00:12:58,640 --> 00:12:59,990
>> Но, се разбира, ова е уште несовршени.

321
00:12:59,990 --> 00:13:00,370
Нели?

322
00:13:00,370 --> 00:13:01,370
Ние си имаат судири.

323
00:13:01,370 --> 00:13:04,680
Повеќе луѓе во овој
податочна структура се уште

324
00:13:04,680 --> 00:13:08,432
ги има истите на раѓање најмалку
ти си без оглед на месец.

325
00:13:08,432 --> 00:13:09,640
Но, она што е направено на авторот?

326
00:13:09,640 --> 00:13:13,427
Па, тоа изгледа како ние имаме низа
на левата страна извлечени вертикално,

327
00:13:13,427 --> 00:13:15,010
но тоа е само препевот уметникот.

328
00:13:15,010 --> 00:13:18,009
Тоа не е важно она што насока сте
подготви низа, тоа е уште една низа.

329
00:13:18,009 --> 00:13:20,225
Што е оваа низа на очигледно?

330
00:13:20,225 --> 00:13:21,500
>> ПУБЛИКАТА: Поврзано листа.

331
00:13:21,500 --> 00:13:21,650
>> DAVID Маланом: Да.

332
00:13:21,650 --> 00:13:23,490
Тоа изгледа како тоа е
низа на поврзани листа.

333
00:13:23,490 --> 00:13:26,490
Значи, повторно, до оваа точка на сортирање
на користење на овие структури на податоци сега

334
00:13:26,490 --> 00:13:28,550
како состојки за да се повеќе
интересни решенија,

335
00:13:28,550 --> 00:13:30,862
сте апсолутно може да потрае
основните, како и низа,

336
00:13:30,862 --> 00:13:33,320
а потоа се земе нешто повеќе
Интересно како се поврзани листа

337
00:13:33,320 --> 00:13:36,660
па дури и да ги комбинирате во уште
повеќе интересни податоци структура.

338
00:13:36,660 --> 00:13:39,630
И навистина, тоа исто така би
да се нарекува hash табелата,

339
00:13:39,630 --> 00:13:42,610
при што низата е
навистина хаш табелата,

340
00:13:42,610 --> 00:13:45,600
но дека хаш табелата има
синџири, би се рекло,

341
00:13:45,600 --> 00:13:50,220
кои може да расте или се намалува врз основа на
број на елементи што сакате да го внесете.

342
00:13:50,220 --> 00:13:52,990
>> Сега, според тоа, она што е
трчање време сега?

343
00:13:52,990 --> 00:13:58,030
Ако сакам да вметнете некој
чиј роденден е 31 октомври,

344
00:13:58,030 --> 00:13:59,040
каде што го прави тој или таа оди?

345
00:13:59,040 --> 00:14:00,530

346
00:14:00,530 --> 00:14:01,030
Добре.

347
00:14:01,030 --> 00:14:02,819
На самото дно каде што вели 31.

348
00:14:02,819 --> 00:14:03,610
И кој е совршен.

349
00:14:03,610 --> 00:14:05,060
Тоа беше константно време.

350
00:14:05,060 --> 00:14:08,760
Но, што ако најдеме некој друг
чиј роденден е, ајде да видиме,

351
00:14:08,760 --> 00:14:10,950
Октомври, Ноември, Декември 31?

352
00:14:10,950 --> 00:14:12,790
Каде е тој или таа се случува да се оди?

353
00:14:12,790 --> 00:14:13,290
Истото.

354
00:14:13,290 --> 00:14:13,970
Два чекора иако.

355
00:14:13,970 --> 00:14:15,303
Тоа е постојан, иако не е тоа?

356
00:14:15,303 --> 00:14:16,360

357
00:14:16,360 --> 00:14:16,860
Добре.

358
00:14:16,860 --> 00:14:17,840
Во моментов тоа е.

359
00:14:17,840 --> 00:14:20,570
Но во општата случај,
повеќе луѓе ќе се додаде,

360
00:14:20,570 --> 00:14:23,790
вероятностно, ние ќе
за да добиете повеќе и повеќе судири.

361
00:14:23,790 --> 00:14:26,820
>> А ова е малку
подобро, бидејќи технички

362
00:14:26,820 --> 00:14:34,580
сега ми синџири може да биде во
најлош случај колку долго?

363
00:14:34,580 --> 00:14:38,890
Ако јас вметнете н луѓето во ова повеќе
софистицирани податоци структура, н луѓе,

364
00:14:38,890 --> 00:14:41,080
во најлош случај тоа се случува да биде n.

365
00:14:41,080 --> 00:14:41,815
Зошто?

366
00:14:41,815 --> 00:14:43,332
>> ПУБЛИКАТА: Затоа што ако сите
ги има истите роденден,

367
00:14:43,332 --> 00:14:44,545
тие се случува да биде една линија.

368
00:14:44,545 --> 00:14:45,420
DAVID Маланом: Совршена.

369
00:14:45,420 --> 00:14:47,480
Тоа може да биде малку смислена,
но навистина во краен случај,

370
00:14:47,480 --> 00:14:50,117
ако секој има иста роденден,
со оглед на влезови што ги имате,

371
00:14:50,117 --> 00:14:51,950
ви се случува да имаат
масовно долг ланец.

372
00:14:51,950 --> 00:14:54,241
И така, можете да го нарекуваме
хаш табелата, но навистина тоа е

373
00:14:54,241 --> 00:14:56,810
само масивна поврзана листа со
едночудо потроши простор.

374
00:14:56,810 --> 00:15:00,460
Но, во принцип, ако се претпостави дека
најмалку родендени се uniform--

375
00:15:00,460 --> 00:15:01,750
и тоа веројатно не е.

376
00:15:01,750 --> 00:15:02,587
Јас сум одлуки дека до.

377
00:15:02,587 --> 00:15:04,420
Но ако претпоставиме, за
заради дискусија

378
00:15:04,420 --> 00:15:07,717
дека тие се, а потоа во теорија, ако
ова е вертикален претставување

379
00:15:07,717 --> 00:15:11,050
на низата, и тогаш се надевам дека сте
случува да се добие ланци кои се, што знаете,

380
00:15:11,050 --> 00:15:15,880
приближно ист должина каде што секој од
овие претставува атом на ден од месеци.

381
00:15:15,880 --> 00:15:19,930
>> Сега, ако има 31 дена во месецот,
тоа значи дека мојата трчање време навистина

382
00:15:19,930 --> 00:15:25,230
е голем O на n над 31, што
се чувствува подобро од линеарна.

383
00:15:25,230 --> 00:15:27,950
Но, она што беше една од нашите
обврски за неколку недели

384
00:15:27,950 --> 00:15:31,145
назад секогаш кога станува збор за изразување
трчање време на алгоритам?

385
00:15:31,145 --> 00:15:33,450

386
00:15:33,450 --> 00:15:35,190
Само само погледнете на висока цел мандат.

387
00:15:35,190 --> 00:15:35,690
Нели?

388
00:15:35,690 --> 00:15:37,400
31 е дефинитивно корисни.

389
00:15:37,400 --> 00:15:39,610
Но ова е сеуште голема O на n.

390
00:15:39,610 --> 00:15:41,730
Но една од темите
на проблемот постави пет

391
00:15:41,730 --> 00:15:43,950
се случува да биде за да се
се признае дека апсолутно,

392
00:15:43,950 --> 00:15:47,320
асимптотично, теоретски
оваа структура на податоци

393
00:15:47,320 --> 00:15:50,470
не постои подобро отколку само
еден масовен поврзана листа.

394
00:15:50,470 --> 00:15:53,550
И навистина, во краен случај, оваа
хаш табелата може да се префрлат во тоа.

395
00:15:53,550 --> 00:15:57,620
>> Но, во реалниот свет, со нас луѓето
дека сопствените Macs или компјутери или што

396
00:15:57,620 --> 00:16:01,240
и се работи реалниот свет
софтвер на реалниот свет на податоци,

397
00:16:01,240 --> 00:16:03,260
кој алгоритам ви се случува да преферираш?

398
00:16:03,260 --> 00:16:09,180
На онаа што го крајот чекори или
оној кој зема N поделено со 31 чекори

399
00:16:09,180 --> 00:16:12,900
да се најдат некои парче на податоци или
да се погледне до некои информации?

400
00:16:12,900 --> 00:16:16,580
Мислам, апсолутно 31 марки
разлика во реалниот свет.

401
00:16:16,580 --> 00:16:18,540
Тоа е 31 пати побрзо.

402
00:16:18,540 --> 00:16:20,880
И ние, луѓето се сигурно
случува да го цениме тоа.

403
00:16:20,880 --> 00:16:23,004
>> Така сфаќаат дихотомијата
таму помеѓу всушност

404
00:16:23,004 --> 00:16:25,920
зборуваме за нешта теоретски
и асимптотично кои дефинитивно

405
00:16:25,920 --> 00:16:28,760
има вредност како што видовме,
но во реалниот свет,

406
00:16:28,760 --> 00:16:32,930
ако се грижите за само правење
человек среќен за основните податоци,

407
00:16:32,930 --> 00:16:36,010
вие многу добро може да сакате да ја прифатите
на фактот дека, да, ова е линеарна,

408
00:16:36,010 --> 00:16:38,360
но тоа е 31 пати побрзо
од линеарна може да биде.

409
00:16:38,360 --> 00:16:41,610
И уште подобро, ние не само што мора да
направи нешто произволно како датум на раѓање,

410
00:16:41,610 --> 00:16:44,030
ние би можеле да поминат малку
повеќе време и мудрост

411
00:16:44,030 --> 00:16:47,140
и мислам за она што може да направи,
Даденото име на една личност, а можеби и

412
00:16:47,140 --> 00:16:50,130
нивниот датум на раѓање за да се комбинираат тие
состојки за да дознаам нешто

413
00:16:50,130 --> 00:16:52,720
што е навистина повеќе
подеднакво и помалку съдран,

414
00:16:52,720 --> 00:16:56,250
така да се каже од оваа слика
моментално укажува дека може да биде.

415
00:16:56,250 --> 00:16:57,750
Како би можеле ние спроведување на оваа во код?

416
00:16:57,750 --> 00:17:00,280
Па, дозволете ми да предложи дека ние
само позајмуваат некои синтакса ние сме

417
00:17:00,280 --> 00:17:01,799
користи неколку пати досега.

418
00:17:01,799 --> 00:17:03,590
И јас одам да се дефинираат
еден јазол, кој повторно

419
00:17:03,590 --> 00:17:06,812
е генерички термин за само некои
контејнер за некои податоци структура.

420
00:17:06,812 --> 00:17:09,020
Одам да се предложи
низ се случува таму.

421
00:17:09,020 --> 00:17:11,369
Но, ние се случува да започнете преземањето
оние обука тркала надвор сега.

422
00:17:11,369 --> 00:17:13,230
>> Нема повеќе CS50 библиотека
навистина, освен ако не сакате

423
00:17:13,230 --> 00:17:15,230
за да го користите за вашиот конечниот
Проектот, кој е во ред,

424
00:17:15,230 --> 00:17:18,569
но сега ние ќе треба да се повлечат
завеса и велат дека тоа е само знак ѕвезда.

425
00:17:18,569 --> 00:17:22,069
Па зборот таму се случува да биде
името на лицето во прашање.

426
00:17:22,069 --> 00:17:25,079
И сега имам врската
тука за да следниот јазол

427
00:17:25,079 --> 00:17:28,170
така што овие претставуваат
секоја од јазли

428
00:17:28,170 --> 00:17:30,950
во синџирот, потенцијално,
на поврзани листа.

429
00:17:30,950 --> 00:17:34,090
>> И сега како да Изјавувам
хаш себе маса?

430
00:17:34,090 --> 00:17:36,660
Как се декларира целата оваа структура?

431
00:17:36,660 --> 00:17:40,960
Па, навистина, слично како јас се користи покажувачот
до само првиот елемент од листа

432
00:17:40,960 --> 00:17:44,510
пред, на сличен начин може да јас само велат
Јас само треба еден куп совети

433
00:17:44,510 --> 00:17:46,270
за спроведување на целата оваа хаш табелата.

434
00:17:46,270 --> 00:17:49,484
Одам да имаат низа
наречен маса за хаш табелата.

435
00:17:49,484 --> 00:17:50,900
Тоа се случува да биде на големината на капацитетите.

436
00:17:50,900 --> 00:17:52,525
Тоа е како многу елементи може да се вклопат во него.

437
00:17:52,525 --> 00:17:56,180
И секоја од овие елементи во оваа
низа ќе биде јазол ѕвезда.

438
00:17:56,180 --> 00:17:56,810
Зошто?

439
00:17:56,810 --> 00:18:00,160
Па, на оваа слика, она што јас сум
спроведување на хаш табелата како

440
00:18:00,160 --> 00:18:04,330
ефективно во почетокот е само
оваа низа дека ние сме извлечат вертикално,

441
00:18:04,330 --> 00:18:06,820
секој од чии квадрати
претставува атом на покажувач.

442
00:18:06,820 --> 00:18:09,170
Дека оние кои имаат засеци
преку нив се само нула.

443
00:18:09,170 --> 00:18:11,410
И оние кои имаат
стрели случува на правото

444
00:18:11,410 --> 00:18:16,140
се вистински совети како да се вистински јазли,
ergo почетокот на поврзани листа.

445
00:18:16,140 --> 00:18:19,050
>> Па еве, тогаш, е како да
спроведување на хаш табелата дека

446
00:18:19,050 --> 00:18:21,580
спроведува посебна врзувањето.

447
00:18:21,580 --> 00:18:22,840
Сега можеме да направиме подобро?

448
00:18:22,840 --> 00:18:25,632
Сите права Обещах последен пат дека
ние може да се постигне постојана време.

449
00:18:25,632 --> 00:18:27,381
И јас вид на ти дал
константно време тука,

450
00:18:27,381 --> 00:18:29,850
но тогаш не рече навистина
константно време, бидејќи тоа е уште

451
00:18:29,850 --> 00:18:31,890
зависни од вкупното
број на елементи

452
00:18:31,890 --> 00:18:34,500
сте внесување во
структурата на податоци.

453
00:18:34,500 --> 00:18:35,980
Но да претпоставиме дека ние го сторивме тоа.

454
00:18:35,980 --> 00:18:39,550
Дозволете ми да се вратиме на екранот овде.

455
00:18:39,550 --> 00:18:44,520
Дозволете ми исто така, проектот ова до тука, јасно
екран, и да претпоставиме дека го направив тоа.

456
00:18:44,520 --> 00:18:49,300
Да претпоставиме дека јас сакав да го вметнете име
Daven во во моите податоци структура.

457
00:18:49,300 --> 00:18:52,100
>> Па сакам да се вметне низ
Daven во податоците структура.

458
00:18:52,100 --> 00:18:54,370
Што ако јас не го користат
хаш табелата, но јас го користам

459
00:18:54,370 --> 00:18:56,980
нешто што е повеќе древовидная
како семејство дрво, каде што

460
00:18:56,980 --> 00:18:59,670
имате некои корен на
врвот, а потоа јазли и лисја

461
00:18:59,670 --> 00:19:01,440
кои одат надолу и нанадвор.

462
00:19:01,440 --> 00:19:04,450
Да претпоставиме дека тогаш, дека јас
сакате да го вметнете Daven е

463
00:19:04,450 --> 00:19:06,430
во она што е во моментов празна листа.

464
00:19:06,430 --> 00:19:09,780
Одам да го направите следново: Јас сум
случува да се создаде еден јазол во оваа фамилија

465
00:19:09,780 --> 00:19:15,170
дрво како структура на податоци, кој изгледа
малку вака, од кои секоја

466
00:19:15,170 --> 00:19:19,640
правоаголници е, да речеме,
за сега 26 елементи во неа.

467
00:19:19,640 --> 00:19:21,650
И секоја од клетките
во оваа низа се случува

468
00:19:21,650 --> 00:19:23,470
да претставуваат писмо на писмото.

469
00:19:23,470 --> 00:19:28,190
>> Поточно, јас ќе одам да се третираат
ова е A, тогаш B, тогаш C, а потоа D,

470
00:19:28,190 --> 00:19:29,310
ова овде.

471
00:19:29,310 --> 00:19:32,940
Така што ова се случува да се ефикасно
претставуваат писмо Д.

472
00:19:32,940 --> 00:19:36,040
Но, за да вметнете сите Daven е
името ми е потребно да се направи малку повеќе.

473
00:19:36,040 --> 00:19:37,840
Па јас сум првиот случува да хаш, така да се каже.

474
00:19:37,840 --> 00:19:41,049
Одам да се погледне на првата буква
в Daven која е очигледно D,

475
00:19:41,049 --> 00:19:42,840
а јас ќе одам да се распределат
еден јазол што изгледа

476
00:19:42,840 --> 00:19:45,570
како this-- голем правоаголник голема
доволно за да ги собере целата азбука.

477
00:19:45,570 --> 00:19:47,140
>> Сега D е направено.

478
00:19:47,140 --> 00:19:49,720
Веднаш A. D-A-V-E-N е цел.

479
00:19:49,720 --> 00:19:51,220
Па сега она што јас ќе одам да направите е ова.

480
00:19:51,220 --> 00:19:54,027
Штом почнав Д известување
нема покажувачот таму.

481
00:19:54,027 --> 00:19:56,860
Тоа е ѓубре вредности во моментот,
или јас да ја иницијализирам на нула.

482
00:19:56,860 --> 00:19:59,630
Но, дозволете ми да продолжувам да одам со
оваа идеја за изградба на дрво.

483
00:19:59,630 --> 00:20:04,260
Дозволете ми да се доделат уште еден од овие
јазли, кој има 26 елементи во неа.

484
00:20:04,260 --> 00:20:05,150
>> И знаете што?

485
00:20:05,150 --> 00:20:09,130
Ако ова е само еден јазол во меморија, која
I создадени со Примерок, со користење на структура

486
00:20:09,130 --> 00:20:11,240
како што наскоро ќе видиме,
Одам да се направи this--

487
00:20:11,240 --> 00:20:14,450
Одам да се подготви стрела
нешто што претставена Д надолу

488
00:20:14,450 --> 00:20:15,860
на оваа нова јазол.

489
00:20:15,860 --> 00:20:19,240
И сега, прв од следниот
писмо во име Daven е,

490
00:20:19,240 --> 00:20:24,150
V-- Д--V-- Одам да се оди напред
и да подготви друг јазол како овој,

491
00:20:24,150 --> 00:20:30,150
при што, на V елементи тука, што
ние ќе се подготви за instance-- Опа.

492
00:20:30,150 --> 00:20:31,020
Ние не ќе ги привлече таму.

493
00:20:31,020 --> 00:20:31,936
Тоа се случува да одат овде.

494
00:20:31,936 --> 00:20:32,890

495
00:20:32,890 --> 00:20:35,712
>> Тогаш ние ќе треба да
сметаат дека тоа е В.

496
00:20:35,712 --> 00:20:44,920
А потоа надолу тука ние ќе да индекс
надолу од V во она што ние ќе се разгледа Е.

497
00:20:44,920 --> 00:20:50,100
А потоа од тука ние ќе го
одат еден од овие јазли тука.

498
00:20:50,100 --> 00:20:52,930
И сега имаме едно прашање да се одговори.

499
00:20:52,930 --> 00:20:57,840
Ми треба некако да се покаже дека
ние сме на крајот од стрингот Daven.

500
00:20:57,840 --> 00:20:59,490
Па јас само би можеле да го оставите нула.

501
00:20:59,490 --> 00:21:02,670
>> Но, што ако имаме Daven е
полно име, исто така, кои

502
00:21:02,670 --> 00:21:04,280
е, како што рековме, Девенпорт?

503
00:21:04,280 --> 00:21:06,970
Па што ако е Daven
всушност подниз,

504
00:21:06,970 --> 00:21:08,960
префикс на многу подолго низ?

505
00:21:08,960 --> 00:21:11,450
Не можеме само трајно
велат ништо не се случува

506
00:21:11,450 --> 00:21:14,410
да се оди таму, затоа што ние би можеле да
никогаш не внесете збор како Девенпорт

507
00:21:14,410 --> 00:21:15,840
во оваа податочна структура

508
00:21:15,840 --> 00:21:19,560
>> Значи она што може да направи наместо да е
лекување на секој од овие елементи

509
00:21:19,560 --> 00:21:22,170
како можеби кој има две
елементи во внатрешноста на нив.

510
00:21:22,170 --> 00:21:24,810
Еден е покажувач, всушност,
како што јас го работам.

511
00:21:24,810 --> 00:21:27,100
Па секоја од овие кутии
не е само една клетка.

512
00:21:27,100 --> 00:21:29,855
Но, што ако на врвот
одно-- дното нечиј

513
00:21:29,855 --> 00:21:32,230
ќе биде нула, бидејќи
не постои Davenport само уште.

514
00:21:32,230 --> 00:21:34,197
Што ако на врвот еден
е некои посебни вредност?

515
00:21:34,197 --> 00:21:36,530
И тоа се случува да биде малку
тешко да се оваа големина се подготви.

516
00:21:36,530 --> 00:21:38,130
Но претпоставувам дека тоа е само знак за проверка.

517
00:21:38,130 --> 00:21:38,920
Провери.

518
00:21:38,920 --> 00:21:44,230
D-A-V-E-N е низа
во оваа структура на податоци.

519
00:21:44,230 --> 00:21:48,350
>> Во меѓувреме, ако имав повеќе простор
тука, јас не можеше да стори П-О-Р-Т,

520
00:21:48,350 --> 00:21:52,650
и јас би можеле да се стави проверка во јазол
кој има букви T на самиот крај.

521
00:21:52,650 --> 00:21:55,460
Па ова е масовно
комплекс изглед податоци структура.

522
00:21:55,460 --> 00:21:57,210
И мојот ракопис
сигурно не помага.

523
00:21:57,210 --> 00:22:00,043
Но, ако сакав да се вметне нешто
друго, сметаат дека она што ние би го направил.

524
00:22:00,043 --> 00:22:03,370
Ако сакаме да се стави Давид,
ние би следат истата логика, Д--V,

525
00:22:03,370 --> 00:22:08,802
но сега јас ќе се истакне во следниот
елемент не од E, но од I до D.

526
00:22:08,802 --> 00:22:10,760
Па таму се случува да биде
повеќе јазли во ова дрво.

527
00:22:10,760 --> 00:22:12,325
Ние се случува да имаат разговор Примерок повеќе.

528
00:22:12,325 --> 00:22:14,700
Но, јас не сакам да се направи
комплетен хаос на оваа слика.

529
00:22:14,700 --> 00:22:17,710
Па ајде наместо да се погледне во едно
тоа е се предформулиран

530
00:22:17,710 --> 00:22:21,810
вака со не точка, точка,
точки, но само со кратенка низи.

531
00:22:21,810 --> 00:22:23,950
Но, секоја од јазли
во ова дрво тука

532
00:22:23,950 --> 00:22:26,700
го претставува истиот thing--
низа Ray на големина 26.

533
00:22:26,700 --> 00:22:28,860
>> Или, ако сакаме да бидеме
навистина соодветна сега, она што

534
00:22:28,860 --> 00:22:30,790
ако нечие име како
апостроф, ајде да

535
00:22:30,790 --> 00:22:35,560
претпостави дека секој јазол всушност има
како 27 индекси во него, а не само 26.

536
00:22:35,560 --> 00:22:42,020
Па ова сега ќе биде на податоци
структура наречена trie-- T-R-I-E.

537
00:22:42,020 --> 00:22:46,120
Trie, која е наводно
историски умен име за дрво

538
00:22:46,120 --> 00:22:49,040
дека е оптимизиран за
пребарување, што се разбира,

539
00:22:49,040 --> 00:22:50,870
е напишано со I-Е па тоа е Trie.

540
00:22:50,870 --> 00:22:52,710
Но, тоа е историја на Trie.

541
00:22:52,710 --> 00:22:55,860
>> Па еден Trie е ова дрво-like податоци
структура како семејно стебло

542
00:22:55,860 --> 00:22:57,510
дека во крајна линија се однесува како тоа.

543
00:22:57,510 --> 00:23:00,890
И тука е само уште еден пример на
куп на имињата на другите луѓе.

544
00:23:00,890 --> 00:23:03,540
Но, прашањето сега
при рака е она што имаат

545
00:23:03,540 --> 00:23:08,070
ние стекнато преку воведување веројатно повеќе
сложен податоци структура, и еден,

546
00:23:08,070 --> 00:23:09,870
искрено, дека го користи многу меморија.

547
00:23:09,870 --> 00:23:11,703
>> Бидејќи иако,
во моментов, јас сум само

548
00:23:11,703 --> 00:23:15,050
користење на покажувачот на D и
И V и Ес и Н.С.,

549
00:23:15,050 --> 00:23:16,700
Јас сум губи подлец на многу меморија.

550
00:23:16,700 --> 00:23:18,030

551
00:23:18,030 --> 00:23:22,660
Но каде што јас поминат еден ресурс,
Имам навика да го добие назад друг.

552
00:23:22,660 --> 00:23:26,020
Значи, ако јас сум трошење повеќе простор,
она што е веројатно надеж?

553
00:23:26,020 --> 00:23:27,407
Дека сум трошат помалку што?

554
00:23:27,407 --> 00:23:28,240
ПУБЛИКАТА: Помалку време.

555
00:23:28,240 --> 00:23:28,990
DAVID Маланом: Време.

556
00:23:28,990 --> 00:23:30,320
А зошто тоа може да биде?

557
00:23:30,320 --> 00:23:33,880
Па, она што е вметнување
време, во однос на големите O момент,

558
00:23:33,880 --> 00:23:37,660
на име како Daven
или Девенпорт или Давид?

559
00:23:37,660 --> 00:23:39,340
Па, Daven беше пет чекори.

560
00:23:39,340 --> 00:23:42,350
Девенпорт ќе биде девет чекори,
па тоа ќе биде уште неколку чекори.

561
00:23:42,350 --> 00:23:44,250
David ќе биде пет чекори, како и.

562
00:23:44,250 --> 00:23:47,230
Значи тоа се бетон
броеви, но сигурно има

563
00:23:47,230 --> 00:23:49,550
горна граница на
Должината на нечие име.

564
00:23:49,550 --> 00:23:52,240
И навистина, во проблемот
комплети од пет спецификација,

565
00:23:52,240 --> 00:23:54,050
ние се случува да се предложи
дека тоа е нешто

566
00:23:54,050 --> 00:23:55,470
тоа е 40-некои-чудно карактери.

567
00:23:55,470 --> 00:23:58,180
>> Реално, никој нема
бескрајно долго име,

568
00:23:58,180 --> 00:24:01,542
што би се рекло, на должината на
име или должината на стрингот ние би можеле да

569
00:24:01,542 --> 00:24:03,750
имаат одредени состојбата на
структура е веројатно она што?

570
00:24:03,750 --> 00:24:05,550

571
00:24:05,550 --> 00:24:06,250
Тоа е константна.

572
00:24:06,250 --> 00:24:06,430
Нели?

573
00:24:06,430 --> 00:24:09,310
Тоа би можело да биде голем постојана како
40-нешто, но тоа е константа.

574
00:24:09,310 --> 00:24:13,752
И тоа нема никаква зависност од тоа колку
други имиња се во оваа податочна структура.

575
00:24:13,752 --> 00:24:15,460
Со други зборови, ако I
сакав да сега вметнете

576
00:24:15,460 --> 00:24:20,540
Колтон или Габриел или Роб или Zamyla или
Alison или Белинда или било која друга називи

577
00:24:20,540 --> 00:24:23,940
од редот на вработените во овие податоци
структура, е трчање време

578
00:24:23,940 --> 00:24:26,750
на вметнување други имиња
нема да биде во сите под влијание

579
00:24:26,750 --> 00:24:30,220
од колку други елементи се
во податоците структура веќе?

580
00:24:30,220 --> 00:24:31,040
Тоа не е.

581
00:24:31,040 --> 00:24:31,540
Нели?

582
00:24:31,540 --> 00:24:36,150
Бидејќи сме ефикасно користење
овој мулти-слој hash табелата.

583
00:24:36,150 --> 00:24:38,280
И трчање време на
било која од овие операции

584
00:24:38,280 --> 00:24:41,510
е зависна не од бројот на
елементи кои се наоѓаат во податоците структура

585
00:24:41,510 --> 00:24:43,090
или кои се на крајот ќе
за да биде во податоците структура,

586
00:24:43,090 --> 00:24:44,714
но од должината на што конкретно?

587
00:24:44,714 --> 00:24:46,500

588
00:24:46,500 --> 00:24:49,200
>> Низ се
вметнати, кој прави

589
00:24:49,200 --> 00:24:52,580
ова асимптотично постојана
time-- голема O на еден.

590
00:24:52,580 --> 00:24:54,720
И искрено, само во
реалниот свет, ова

591
00:24:54,720 --> 00:24:58,380
значи вметнување на името Daven зема
како пет чекори, или Девенпорт девет

592
00:24:58,380 --> 00:25:00,100
чекори, или David пет чекори.

593
00:25:00,100 --> 00:25:03,071
Тоа е прилично ебам мали трчање пати.

594
00:25:03,071 --> 00:25:05,320
И, навистина, тоа е многу
добра работа, особено кога

595
00:25:05,320 --> 00:25:08,126
тоа не е зависен од вкупното
број на елементи во таму.

596
00:25:08,126 --> 00:25:10,500
Па како да се спроведе овој
вид на структура во код?

597
00:25:10,500 --> 00:25:12,900
Тоа е малку повеќе
комплекс, но сепак тоа е

598
00:25:12,900 --> 00:25:15,050
само примена на
основните градежни блокови.

599
00:25:15,050 --> 00:25:17,830
Одам да се редефинира
ни јазол како што следува:

600
00:25:17,830 --> 00:25:21,100
bool наречен word-- и ова
може да се нарече ништо.

601
00:25:21,100 --> 00:25:23,970
Но bool претставува
она што го изведов како знак за проверка.

602
00:25:23,970 --> 00:25:24,490
Да.

603
00:25:24,490 --> 00:25:26,720
Ова е крајот на низа
во оваа структура на податоци.

604
00:25:26,720 --> 00:25:30,702
>> И, се разбира, на јазол звезда
таму е се однесува на деца.

605
00:25:30,702 --> 00:25:32,410
И, навистина, само се допаѓа
семејно стебло,

606
00:25:32,410 --> 00:25:34,370
ќе ја разгледа јазли
кои се виси

607
00:25:34,370 --> 00:25:36,920
на дното на некои родител
елемент да бидат деца.

608
00:25:36,920 --> 00:25:40,510
И така децата ќе се
да се низа на 27, на 27-едно

609
00:25:40,510 --> 00:25:41,680
само да биде за апостроф.

610
00:25:41,680 --> 00:25:43,390
Ние си оди за да се најде решение
на посебен случај тоа.

611
00:25:43,390 --> 00:25:45,400
Па можете да имате одредени
имињата со апострофи.

612
00:25:45,400 --> 00:25:47,399
Можеби дури и цртичка треба
одат во таму, но ќе

613
00:25:47,399 --> 00:25:50,330
види во п сет 5 ние само грижа
за писма и апострофи.

614
00:25:50,330 --> 00:25:52,990
>> А потоа како го претставуваат
податоците себе структура?

615
00:25:52,990 --> 00:25:56,454
Како не ви претставуваат корен
на овој Trie, така да зборуваш?

616
00:25:56,454 --> 00:25:59,620
Па, само се допаѓа со поврзана листа, можете
треба покажувач на првиот елемент.

617
00:25:59,620 --> 00:26:04,270
Со Trie вие само треба еден
Покажувач на коренот на оваа Trie.

618
00:26:04,270 --> 00:26:07,290
И од таму може да хаш
на вашиот пат надолу подлабоко и подлабоко

619
00:26:07,290 --> 00:26:10,460
за секој друг јазол во структурата.

620
00:26:10,460 --> 00:26:13,440
Па едноставно со ова може
ние ги претставуваме дека структура.

621
00:26:13,440 --> 00:26:15,877
>> Сега Meanwhile-- О, прашање.

622
00:26:15,877 --> 00:26:17,220
>> ПУБЛИКАТА: Што е bool збор?

623
00:26:17,220 --> 00:26:20,490
>> DAVID Маланом: bool збор е
само оваа C инкарнација

624
00:26:20,490 --> 00:26:22,920
на она што јас го опиша
во ова поле тука, кога

625
00:26:22,920 --> 00:26:26,000
Почнав со расцепувањето на секој од
елементи во две парчиња низа е.

626
00:26:26,000 --> 00:26:27,600
Еден е покажувач кон следниот јазол.

627
00:26:27,600 --> 00:26:30,280
На други треба да биде
нешто како наога

628
00:26:30,280 --> 00:26:33,770
да се каже да, има
Зборот Daven која завршува тука,

629
00:26:33,770 --> 00:26:35,610
затоа што не сакаме,
во моментот, Дејв.

630
00:26:35,610 --> 00:26:39,320
>> И покрај тоа што Dave се случува да биде
легитимни збор, тој не е во Trie

631
00:26:39,320 --> 00:26:39,830
уште.

632
00:26:39,830 --> 00:26:40,950
И D не е збор.

633
00:26:40,950 --> 00:26:42,770
И Г-не е збор или име.

634
00:26:42,770 --> 00:26:45,020
Така штиклирање
укажува само еднаш сте

635
00:26:45,020 --> 00:26:48,190
погоди овој јазол е
претходниот пат на карактери

636
00:26:48,190 --> 00:26:50,700
всушност низ кои сте поставена.

637
00:26:50,700 --> 00:26:53,660
Значи тоа е сите bool
таму се прави за нас.

638
00:26:53,660 --> 00:26:55,500
>> Било какви други прашања на обиди?

639
00:26:55,500 --> 00:26:56,215
Да.

640
00:26:56,215 --> 00:26:58,035
>> ПУБЛИКАТА: Што е преклопување?

641
00:26:58,035 --> 00:26:59,945
Што ако имате Дејв и Daven?

642
00:26:59,945 --> 00:27:00,820
DAVID Маланом: Совршена.

643
00:27:00,820 --> 00:27:02,580
Што ако имате Дејв и Daven?

644
00:27:02,580 --> 00:27:06,240
Значи, ако ние се вметне, велат прекар,
за David-- Dave-- D-A-V-E?

645
00:27:06,240 --> 00:27:07,370

646
00:27:07,370 --> 00:27:08,700
Ова е всушност супер едноставен.

647
00:27:08,700 --> 00:27:10,325
Па ние сме само ќе ги преземе четирите чекори.

648
00:27:10,325 --> 00:27:11,042

649
00:27:11,042 --> 00:27:15,847
D-A-V-E. И она што морам да
направи еднаш ја удирам дека четвртата јазол?

650
00:27:15,847 --> 00:27:16,680
Само случува да се провери.

651
00:27:16,680 --> 00:27:18,000
Ние сме веќе добро да отидевме.

652
00:27:18,000 --> 00:27:18,840
Направи.

653
00:27:18,840 --> 00:27:19,750
Четири чекори.

654
00:27:19,750 --> 00:27:21,590
Константно време асимптотично.

655
00:27:21,590 --> 00:27:26,300
И сега ние сме посочи дека двете Дејв
и Daven се стрингови во структурата.

656
00:27:26,300 --> 00:27:27,710
Па не е проблем.

657
00:27:27,710 --> 00:27:30,200
И ќе забележите како присуство
на Daven не го направи

658
00:27:30,200 --> 00:27:34,750
земе повеќе време или помалку
време за Дејв и обратно.

659
00:27:34,750 --> 00:27:36,000
>> Па што друго можеме сега направам?

660
00:27:36,000 --> 00:27:40,680
Ние сме се користи оваа метафора пред
на пепелниците ги претставуваат нешто.

661
00:27:40,680 --> 00:27:43,380
Но излегува дека
магацинот на пепелниците е, всушност,

662
00:27:43,380 --> 00:27:47,187
демонстративен на друга апстрактни податоци
type-- повисоко ниво на податочна структура

663
00:27:47,187 --> 00:27:49,770
дека на крајот на денот е само
како низа или поврзано листа

664
00:27:49,770 --> 00:27:50,970
или нешто повеќе светски.

665
00:27:50,970 --> 00:27:53,270
Но, тоа е повеќе интересно
концептуална концепт.

666
00:27:53,270 --> 00:27:56,440
Магацинот, како овие
Табли тука во Mather,

667
00:27:56,440 --> 00:27:58,750
обично се нарекува
само that-- оџак.

668
00:27:58,750 --> 00:28:02,540
>> И во овој тип на податоци структура
имате две операции-

669
00:28:02,540 --> 00:28:05,880
имате еден вика притисок за
додавање на нешто до магацинот,

670
00:28:05,880 --> 00:28:08,320
како ставање друга тава
назад на врвот на магацинот.

671
00:28:08,320 --> 00:28:11,350
А потоа поп, кој ви значи
земе врвниот тава надвор.

672
00:28:11,350 --> 00:28:16,210
Но, она што е клучот за стек е дека
тоа е се здобија овој љубопитни карактеристика.

673
00:28:16,210 --> 00:28:19,560
Како јадење салата персонал
преуредување на коцки за следниот оброк,

674
00:28:19,560 --> 00:28:21,380
она што се случува да биде
точно за тоа како студентите

675
00:28:21,380 --> 00:28:22,856
во интеракција со оваа структура на податоци?

676
00:28:22,856 --> 00:28:24,480
ПУБЛИКАТА: Тие се случува да pop еднократна.

677
00:28:24,480 --> 00:28:26,550
DAVID Маланом: Тие се случува да се
поп еднократна, се надевам на врвот.

678
00:28:26,550 --> 00:28:28,910
Инаку тоа е само вид на глупави
да одат по целиот пат до дното.

679
00:28:28,910 --> 00:28:29,070
Нели?

680
00:28:29,070 --> 00:28:31,620
Структура на податоци всушност не се овозможи
можете да го дофати дното табла најмалку

681
00:28:31,620 --> 00:28:32,520
лесно.

682
00:28:32,520 --> 00:28:35,040
Па таму е овој љубопитен
имот на оџакот

683
00:28:35,040 --> 00:28:39,730
дека последната точка во е
случува да биде првиот надвор.

684
00:28:39,730 --> 00:28:43,400
И компјутерски научници се јавите
оваа LIFO-- да трае во, прв надвор.

685
00:28:43,400 --> 00:28:45,540
А тоа всушност мора
интересни апликации.

686
00:28:45,540 --> 00:28:50,090
Тоа не е нужно толку очигледни како што некои
другите, но тоа може да се, всушност, да биде корисен,

687
00:28:50,090 --> 00:28:54,040
и тоа може, всушност, да се спроведува
во неколку различни начини.

688
00:28:54,040 --> 00:28:58,550
>> Значи еден, а всушност, нека
мене не да се нурне во тоа.

689
00:28:58,550 --> 00:28:59,860
Ајде да го направите ова, наместо.

690
00:28:59,860 --> 00:29:03,700
Ајде да погледнеме во еден кој е речиси
истата идеја, но тоа е малку пофер.

691
00:29:03,700 --> 00:29:04,200
Нели?

692
00:29:04,200 --> 00:29:07,560
Ако сте еден од овие фан момчиња или
девојки кои навистина сака Apple производи

693
00:29:07,560 --> 00:29:10,130
и ви се разбудив во 03:00
да се редат на некои продавница

694
00:29:10,130 --> 00:29:14,150
за да го добиете најновите iPhone,
би можело да чекаат на ред се допаѓа ова.

695
00:29:14,150 --> 00:29:15,800
>> Сега ред е многу намерно име.

696
00:29:15,800 --> 00:29:18,190
Тоа е линија поради тоа што има
некои правичноста на него.

697
00:29:18,190 --> 00:29:18,690
Нели?

698
00:29:18,690 --> 00:29:21,690
Тој вид на ќе вовлечени ако сте
стигнавме таму прв на Apple продавница

699
00:29:21,690 --> 00:29:25,700
но вие сте ефикасно долното
тава, бидејќи вработените Епл потоа

700
00:29:25,700 --> 00:29:28,189
поп последниот човек кој
всушност доби по ред.

701
00:29:28,189 --> 00:29:31,230
Па купчињата и редици, иако
функционално тие се вид на same--

702
00:29:31,230 --> 00:29:33,105
тоа е само оваа збирка
на ресурси кои е

703
00:29:33,105 --> 00:29:36,210
ќе расте и shrink-- има
оваа праведност аспект на тоа,

704
00:29:36,210 --> 00:29:39,634
барем во реалниот свет,
каде операции ќе се вежба

705
00:29:39,634 --> 00:29:40,800
се фундаментално различни.

706
00:29:40,800 --> 00:29:43,360
Stack-- опашка
rather-- се вели дека имаат

707
00:29:43,360 --> 00:29:45,320
две операции: n опашка и г опашка.

708
00:29:45,320 --> 00:29:46,341

709
00:29:46,341 --> 00:29:48,090
Или можете да ги нарекуваат
било кој број на нештата.

710
00:29:48,090 --> 00:29:50,770
Но само сакате да го фати
поимот дека еден е додавање

711
00:29:50,770 --> 00:29:53,230
и едно е во крајна линија со одземање.

712
00:29:53,230 --> 00:29:58,840
>> Сега под хаубата, и на магацинот
и редот може да се спроведува како?

713
00:29:58,840 --> 00:30:01,390
Ние нема да одам во кодот на
него, бидејќи на повисоко ниво

714
00:30:01,390 --> 00:30:03,387
Идејата е вид на повеќе од очигледна.

715
00:30:03,387 --> 00:30:04,470
Мислам, она што луѓето го прават?

716
00:30:04,470 --> 00:30:07,030
Ако јас сум првиот човек на Епл
Чување и ова е на влезната врата,

717
00:30:07,030 --> 00:30:08,130
што знаете, јас ќе одам да се застане тука.

718
00:30:08,130 --> 00:30:09,750
И следниот лице
се случува да застане тука.

719
00:30:09,750 --> 00:30:11,500
И следниот лице
се случува да застане тука.

720
00:30:11,500 --> 00:30:13,792
Па што податочна структура
е подложна на дното?

721
00:30:13,792 --> 00:30:14,542
>> ПУБЛИКАТА: опашка.

722
00:30:14,542 --> 00:30:15,667
DAVID Маланом: Па, на опашката.

723
00:30:15,667 --> 00:30:16,390
Сигурен.

724
00:30:16,390 --> 00:30:16,920
Што друго?

725
00:30:16,920 --> 00:30:17,600
>> ПУБЛИКАТА: поврзани листа.

726
00:30:17,600 --> 00:30:18,990
>> DAVID Маланом: поврзани
листа можете да ги спроведе.

727
00:30:18,990 --> 00:30:22,500
И поврзана листа е убаво затоа што тогаш
тоа може да расте произволно долго како што се противат

728
00:30:22,500 --> 00:30:24,880
да има некои фиксен број
на луѓе во продавницата.

729
00:30:24,880 --> 00:30:27,030
Но, можеби и фиксен број
на места е легитимна.

730
00:30:27,030 --> 00:30:30,350
Бидејќи ако тие имаат само како 20
iPhone-на првиот ден, можеби

731
00:30:30,350 --> 00:30:33,930
тие треба само низа од големината
20 до претставуваат дека на дното, која

732
00:30:33,930 --> 00:30:37,070
е само да се каже сега еднаш ние да почнам да зборувам
за овие повисоко ниво проблеми,

733
00:30:37,070 --> 00:30:38,890
можете да го имплементира
во било кој број на начини.

734
00:30:38,890 --> 00:30:42,030
И таму е веројатно само ќе се
да се исклучи трговија во просторот и времето

735
00:30:42,030 --> 00:30:43,950
или само во свој код комплексност.

736
00:30:43,950 --> 00:30:45,380
>> Она што за оџакот?

737
00:30:45,380 --> 00:30:48,190
Па, говедо, видовме премногу
само би можеле да бидат овие коцки.

738
00:30:48,190 --> 00:30:50,007
И можете да ја имплементираат оваа низа.

739
00:30:50,007 --> 00:30:53,090
Но во некоја точка, ако имате потреба при користење низа,
што ќе се случи со тави

740
00:30:53,090 --> 00:30:54,173
сте се обидува да се спушти?

741
00:30:54,173 --> 00:30:55,170

742
00:30:55,170 --> 00:30:55,670
Добре.

743
00:30:55,670 --> 00:30:57,490
Ти си само ќе
да можат да одат толку висока.

744
00:30:57,490 --> 00:31:00,156
И мислам дека во Mather тие се
всушност вдлабнати со тоа, што отворот.

745
00:31:00,156 --> 00:31:01,950
Па навистина, тоа е речиси
како Mather е со користење на

746
00:31:01,950 --> 00:31:03,783
низа на фиксна големина,
зашто можеш само

747
00:31:03,783 --> 00:31:08,302
одговара на толку многу пепелниците со тоа, што се отвора во
ѕидот долу колена луѓето.

748
00:31:08,302 --> 00:31:10,010
И, така што може да биде
вели дека е низа,

749
00:31:10,010 --> 00:31:14,300
но ние сигурно би можеле да спроведат дека
поопшто со поврзана листа.

750
00:31:14,300 --> 00:31:16,390
>> Па, она што за друг податочна структура?

751
00:31:16,390 --> 00:31:18,760
Дозволете ми да се повлече до еден други визуелни тука.

752
00:31:18,760 --> 00:31:24,710
Нешто како како за овој овде?

753
00:31:24,710 --> 00:31:28,920
Зошто може да биде корисно за да не мора
нешто како фенси како Trie, која

754
00:31:28,920 --> 00:31:32,370
што гледаме овие многу широк јазли,
од кои секој е во низа?

755
00:31:32,370 --> 00:31:35,740
Но, што ако правиме нешто повеќе
едноставно, како старата школа семејно стебло,

756
00:31:35,740 --> 00:31:38,110
секој од чии јазли тука
е само чување на голем број.

757
00:31:38,110 --> 00:31:42,180
Наместо името или потомок
е само чување на број како оваа.

758
00:31:42,180 --> 00:31:45,250
>> Па, жаргон ние ги користиме во
структури на податоци е и обиди

759
00:31:45,250 --> 00:31:49,510
и дрва, каде што еден Trie, повторно, е
само еден чии јазли се низи,

760
00:31:49,510 --> 00:31:51,680
се уште е она што може да
користите од основно училиште

761
00:31:51,680 --> 00:31:53,860
кога ќе се направи семејство
tree-- листови и корен

762
00:31:53,860 --> 00:31:57,250
на дрво и деца на
родителите и браќата и сестрите од него.

763
00:31:57,250 --> 00:32:03,670
И ние може да се спроведе дрво,
на пример, како што е едноставно како ова.

764
00:32:03,670 --> 00:32:07,420
Дрво, ако тоа како јазол, еден од
овие кругови што има голем број,

765
00:32:07,420 --> 00:32:09,947
тоа не се случува да имаат
еден покажувач, туку две.

766
00:32:09,947 --> 00:32:11,780
И веднаш штом ќе додадете
втор покажувач, ти

767
00:32:11,780 --> 00:32:13,905
всушност може да сега се направи вид
на две-димензионална податоци

768
00:32:13,905 --> 00:32:14,780
структури во меморијата.

769
00:32:14,780 --> 00:32:16,660
Многу како дво-димензионална
низа, можете

770
00:32:16,660 --> 00:32:18,904
имаат вид на две-димензионална
поврзани листи, но оние

771
00:32:18,904 --> 00:32:20,820
кои го следат моделот
каде што нема циклуси.

772
00:32:20,820 --> 00:32:24,487
Тоа е навистина дрво со еден
баба или дедо пат до тука, а потоа

773
00:32:24,487 --> 00:32:27,320
некои родители и деца и
внуци и правнуци.

774
00:32:27,320 --> 00:32:28,370
и така натаму.

775
00:32:28,370 --> 00:32:32,390
>> Но она што е навистина уредни за овој исто така,
само за да ви закачам со малку код,

776
00:32:32,390 --> 00:32:35,370
потсетиме рекурзијата од
некое време назад, при што

777
00:32:35,370 --> 00:32:38,220
ти пишувам функција која се нарекува себеси.

778
00:32:38,220 --> 00:32:41,140
Ова е прекрасна можност
за спроведување на нешто

779
00:32:41,140 --> 00:32:42,920
како рекурзија, бидејќи сметаат дека ова.

780
00:32:42,920 --> 00:32:43,860
>> Оваа е дрво.

781
00:32:43,860 --> 00:32:48,040
И јас сум бил малку анален со тоа како
Го ставам на цели броеви на улица.

782
00:32:48,040 --> 00:32:51,020
Толку многу што тој има посебен
name-- бинарни пребарување дрво.

783
00:32:51,020 --> 00:32:53,460
Сега сме слушнале од бинарни
пребарување, но може да ви

784
00:32:53,460 --> 00:32:55,180
работат наназад од името оваа работа е?

785
00:32:55,180 --> 00:32:59,280
Што е шемата за тоа како I
вметнале цели броеви во ова дрво?

786
00:32:59,280 --> 00:33:00,696
Тоа не е произволно.

787
00:33:00,696 --> 00:33:01,570
Там-то шема.

788
00:33:01,570 --> 00:33:02,090
Да.

789
00:33:02,090 --> 00:33:03,370
>> ПУБЛИКАТА: помалите на левата страна.

790
00:33:03,370 --> 00:33:03,690
>> DAVID Маланом: Да.

791
00:33:03,690 --> 00:33:05,062
Помалите се на левата страна.

792
00:33:05,062 --> 00:33:06,270
Поголемите на прав.

793
00:33:06,270 --> 00:33:12,940
Таква што вистински изјава е
родител е поголема од неговата лева дете,

794
00:33:12,940 --> 00:33:14,850
но помалку од неговите право дете.

795
00:33:14,850 --> 00:33:17,750
И само тоа е дури и
рекурзивен вербална дефиниција

796
00:33:17,750 --> 00:33:20,500
бидејќи можете да го применат тоа
истата логика на секој јазол

797
00:33:20,500 --> 00:33:23,080
и тоа само долен дел
надвор, база случај ако

798
00:33:23,080 --> 00:33:25,740
ќе, кога ќе удри еден од
листа, така да се каже,

799
00:33:25,740 --> 00:33:28,580
каде што еден отсуство нема деца понатаму.

800
00:33:28,580 --> 00:33:30,614
>> Сега како може да ви се најде бројот 44?

801
00:33:30,614 --> 00:33:32,280
Ќе започне во коренот и да кажам, хм.

802
00:33:32,280 --> 00:33:35,690
55 не е 44 И така, да сакам да одам
право или не сакам да оди лево?

803
00:33:35,690 --> 00:33:37,190
Па, очигледно сакате да одите лево.

804
00:33:37,190 --> 00:33:40,060
И така тоа е само како телефон
книга пример во бинарна пребарување

805
00:33:40,060 --> 00:33:41,099
генерално.

806
00:33:41,099 --> 00:33:43,390
Но, ние сме нејзиното спроведување
сега малку повеќе динамички

807
00:33:43,390 --> 00:33:45,339
од низа може да им овозможи на.

808
00:33:45,339 --> 00:33:48,130
И всушност, ако сакате да се погледне
на кодот, на прв поглед сигурно.

809
00:33:48,130 --> 00:33:49,671
Тоа изгледа како куп линии.

810
00:33:49,671 --> 00:33:51,220
Но, тоа е убаво едноставна.

811
00:33:51,220 --> 00:33:54,490
Ако сакате да се имплементираат функција
наречен пребарување чија цел во животот

812
00:33:54,490 --> 00:33:57,290
е да пребарување за вредност
како n, цел број,

813
00:33:57,290 --> 00:34:01,756
а ти си поминале во еден pointer--
покажувач на јазол на корените,

814
00:34:01,756 --> 00:34:04,380
поточно, на тоа дрво, од кои
можете да пристапите сè друго,

815
00:34:04,380 --> 00:34:08,850
се забележи како на вистината
може да се спроведе логика.

816
00:34:08,850 --> 00:34:10,880
Ако дрвото е нула,
Очигледно, тоа не е таму.

817
00:34:10,880 --> 00:34:11,880
Ајде само return false.

818
00:34:11,880 --> 00:34:12,000
Нели?

819
00:34:12,000 --> 00:34:14,040
Ако го предаде ништо,
таму нема ништо.

820
00:34:14,040 --> 00:34:17,900
>> Друго, ако n е помал од
дрво стрелка N-- сега стрелка н,

821
00:34:17,900 --> 00:34:20,670
потсетиме воведовме супер
кратко пред некој ден,

822
00:34:20,670 --> 00:34:25,100
и тоа само значи de-референца
покажувач и се погледне на областа наречена н.

823
00:34:25,100 --> 00:34:27,690
Па тоа значи одиме таму и
погледнете во областа наречена н.

824
00:34:27,690 --> 00:34:33,810
Значи, ако н, вредноста сте дадено, е помалку
од вредноста на дрво integer,

825
00:34:33,810 --> 00:34:35,449
Каде сакаш да одиме?

826
00:34:35,449 --> 00:34:36,389
Вляво.

827
00:34:36,389 --> 00:34:37,780
>> Така забележите рекурзијата.

828
00:34:37,780 --> 00:34:39,860
Јас сум returning-- не е точно.

829
00:34:39,860 --> 00:34:40,989
Не е неточно.

830
00:34:40,989 --> 00:34:45,670
Јас сум се враќа без оглед на одговорот
е од повик за себе, минувајќи

831
00:34:45,670 --> 00:34:50,100
n пак, кој е вишок,
но она што е малку различни сега?

832
00:34:50,100 --> 00:34:51,989
Како јас што го прави проблемот помали?

833
00:34:51,989 --> 00:34:54,920
Јас кој поминува во како втор
аргумент, а не на коренот на дрвото,

834
00:34:54,920 --> 00:34:59,616
но на левата дете во овој случај.

835
00:34:59,616 --> 00:35:00,990
Па јас сум поминува во левата дете.

836
00:35:00,990 --> 00:35:04,720
>> Во меѓувреме, ако n е поголема од
јазол Јас сум во моментов во потрага по,

837
00:35:04,720 --> 00:35:06,690
Јас пребарување на десната страна.

838
00:35:06,690 --> 00:35:10,880
Друго, ако на дрвото не е нула, и
ако елементот не е од лево

839
00:35:10,880 --> 00:35:13,240
и тоа не е на правото,
она што е прекрасно случај?

840
00:35:13,240 --> 00:35:14,630

841
00:35:14,630 --> 00:35:18,440
Ние сме всушност се најде јазол во
прашање, и така ние се врати вистина.

842
00:35:18,440 --> 00:35:21,490
>> Па ние само изгребани на површината
сега некои од овие структури на податоци.

843
00:35:21,490 --> 00:35:24,370
Во проблем постави пет испишан
истражуваат овие уште понатаму,

844
00:35:24,370 --> 00:35:27,250
и ќе ви биде дадена вашиот дизајн
избор за тоа како да се обратите за ова.

845
00:35:27,250 --> 00:35:30,250
Што би сакал да се заклучи на
е само 30 секунди закачка

846
00:35:30,250 --> 00:35:32,080
на она што го чека следната недела и пошироко.

847
00:35:32,080 --> 00:35:35,390
>> Како што ние begin-- за среќа можеби ќе
think-- нашата транзиција бавно

848
00:35:35,390 --> 00:35:38,680
од светот на C и долните
имплементација ниво детали,

849
00:35:38,680 --> 00:35:42,090
до свет во кој можеме да ги преземат за
готово дека некој друг има конечно

850
00:35:42,090 --> 00:35:44,010
спроведува овие податоци
структури за нас,

851
00:35:44,010 --> 00:35:47,570
и ние ќе почнеме да го разбираме
реалниот свет средства за спроведување на

852
00:35:47,570 --> 00:35:50,560
web-базирани на програми и
интернет на генерално

853
00:35:50,560 --> 00:35:52,910
и, исто така, многу сигурност
импликации дека ние сме само

854
00:35:52,910 --> 00:35:54,850
почна да гребење на површината на.

855
00:35:54,850 --> 00:35:57,320
Овде е она што не чека
во деновите што доаѓаат.

856
00:35:57,320 --> 00:36:00,480
>> [Видео репродукција]

857
00:36:00,480 --> 00:36:03,432

858
00:36:03,432 --> 00:36:12,780
>> -Той Дојде со порака,
со записник сите свои.

859
00:36:12,780 --> 00:36:26,110

860
00:36:26,110 --> 00:36:30,894
Тој дојде во светот на суров
firewalls, незасегнатата рутери,

861
00:36:30,894 --> 00:36:33,368
и опасностите далеку полошо од смртта.

862
00:36:33,368 --> 00:36:35,280

863
00:36:35,280 --> 00:36:36,236
Тој е брз.

864
00:36:36,236 --> 00:36:37,980
Тој е силен.

865
00:36:37,980 --> 00:36:42,830
Тој е TCP / IP, и тој доби вашата адреса.

866
00:36:42,830 --> 00:36:45,290

867
00:36:45,290 --> 00:36:48,074
"Воини на мрежата."

868
00:36:48,074 --> 00:36:49,660
[END видео репродукција]

869
00:36:49,660 --> 00:36:50,910
DAVID Маланом: следната недела пришествие.

870
00:36:50,910 --> 00:36:51,880
Ние ќе се видиме тогаш.

871
00:36:51,880 --> 00:36:54,615

872
00:36:54,615 --> 00:36:56,060
[Видео репродукција]

873
00:36:56,060 --> 00:36:59,240
-И Сега, "длабоки мисли"
од Daven Фарнхам.

874
00:36:59,240 --> 00:37:02,030

875
00:37:02,030 --> 00:37:05,820
-Дэвид Секогаш започнува
предавања со, "Сите во право."

876
00:37:05,820 --> 00:37:08,750
Зошто да не, "Еве решение
на оваа недела проблем во собата "

877
00:37:08,750 --> 00:37:12,180
или "Ние даваме на сите вас?"

878
00:37:12,180 --> 00:37:13,380
[Се смее]

879
00:37:13,380 --> 00:37:15,530
[END видео репродукција]