So we've talked about how your code
could be slow because the type of
hardware that's executing underneath it,
remember the whole floating
point branching issue problem?
Well, that's mostly a non-issue for
today's hardware.
There's one set of issues that you
still need to worry about, that is,
the performance of the primitives
in the language that you are using.
Take a fundamental
algorithm such as sorting.
Now there are many
ways in which to sort,
and some are better than others,
depending on the circumstances.
For examples, quicksort is generally
faster than bubble sort except when you
have a fewer than a thousand elements or
take searching for
objects in a large sorted list.
Generally, the best way to do
this is with a binary search.
But completely different is finding
objects in an unsorted array.
Now instead of in comparing each object
for the value you're looking for,
you can use a hash function
to find it immediately.
Now this is all basic canon of modern
computer science and data structures.
And thankfully, modern languages like
Java supply these containers and
algorithms on your behalf, so that
you don't have to rewrite the Murmur
3 Hash function or a quicksort over and
over and over again.
But let me reveal something here.
In all of my years of programming,
the one problem that consistently
bites performance of your project
has to do with the performance of these
language-provided container objects.
I mean, it's awesome, right?
Java's providing you with
an implementation of a vector class that
you can push, pop, add, and
remove objects as you see fit, but
in order to get that flexibility, it has
to use a linked list structure under
the hood, which has a unique set
of performance characteristics.
As long as you are only operating on
the front of the list, it's super fast.
But if you're trying to insert or
remove in other places, it's going to
default to the worst possible time.
The point is that just because
the underlying system provides
these containers doesn't mean
that they're performant with
respect to how your program is
going to actually be using them.
James Sutherland published a series of
microbenchmarks on the performance of
specific data structures provided
by the Java framework and
found that there's some differences
in performance versus functionality
that people need to be aware of.
For example,
he found that Hashtable performance
was about 22% faster
than HashMap performance,
depending on how you're actually
using the containers themselves.
The point is this.
Have you profiled your container
classes that you're using in your code?
Are you confident that they are using
the absolute fastest container for
what your code is actually doing?
Mm, yeah, that's what I thought.
But the good news is that you can gain
visibility into the performance of these
containers with some handy
profiling MPIs in Android.
So let's see if Chris's code
stands up to our scrutiny.
إذن فقد تحدثنا عن كيف يمكن
للكود أن يكون بطيئًا بسبب نوع
المكونات المادية التي يعمل من خلالها،
هل تذكر مشكلة موضوع التفريع
الخاص بالعدد ذي الفاصلة العائمة؟
حسنًا، هذا ليس بمشكلة على الإطلاق
بالنسبة لموضوعنا اليوم.
هناك مجموعة من المشاكل
التي ما تزال لتقلق بسببها،
وهي أداء الأساسيات (الأوليات)
في اللغة التي تستخدمها.
ولنأخذ مثالًا على ذلك من
الخوارزميات الرئيسية مثل الترتيب.
هناك الكثير من الطرق
التي يمكن الترتيب من خلالها،
وبعضها أفضل من بعض،
بناءً على الظروف.
مثلًا: خوارزمية الترتيب السريع
أسرع بشكل عام من خوارزمية الفقاعات
إلا في حالة إذا كان لديك أقل من ألف عنصر
أو كنت تقوم ببحث عن عناصر
موجودة ضمن قائمة مصنفة كبيرة.
بوجه عام، أفضل طريقة لفعل ذلك
هي من خلال البحث الثنائي.
لكن وعلى العكس تمامًا يكون العثور
على الكائنات في صفيف غير مصنف.
الآن وبدلًا عن مقارنة كل كائن
بالقيمة التي تبحث عنها،
يمكنك استخدام دالة تجزئة (هاش)
للعثور عليها فورًا.
هذه هي كل القواعد لعلم الحاسوب الحديث
وبنيات البيانات.
ولحسن الحظ، تقوم اللغات الحديثة
مثل جافا بتعبئة هذه الحاويات
والخوارزميات نيابة عنك،
ولذا فأنت لست مضطرًا لإعادة كتابة
3 دوال تجزئة (هاش) أو دالة الترتيب السريع
العديد من المرات مجددًا.
لكن دعني أخبرك شيئًا هنا.
خلال سنوات عملي في البرمجة،
وجدت أن المشكلة الوحيدة
التي تقلل أداء مشروعك بشكل ثابت
لها علاقة بأداء حاويات الكائنات التي
توفرها اللغة.
أعني، هذا مذهل، أليس كذلك؟
تقوم جافا بتزويدك بتنفيذ
فئة بيانات اتجاهية
حيث يمكنك دفع وإظهار وإضافة وحذف الكائنات
حسبما هو ملائم لك،
لكن من أجل الحصول على تلك المرونة،
لا بد أن تستخدم بنية لقائمة متصلة
بالداخل، والتي يكون لديها
مجموعة موحدة من سمات الأداء.
وطالما أنك تقوم بالعمل على واجهة
القائمة فحسب، فستكون سريعة جدًا.
أما إن حاولت الإدراج
أو الحذف في أماكن أخرى، فستقوم بالعودة
إلى الافتراضي في أسوأ توقيت ممكن.
والفكرة هي أنه بسبب النظام الأساسي
الذي يزود هذه الحاويات فحسب
ولا يعني هذا أنها هائلة الأداء
بالنسبة لكيفية استخدام
البرنامج لها في الواقع.
قام جيمس سوثرلاند بنشر سلسلة
من النقاط المرجعية الصغيرة في أداء
هياكل بيانات محددة
مقدمة من إطار عمل جافا
واكتشف أن هناك بعض الاختلافات
في الأداء مقابل التشغيل
والتي يجب أن يعيها الناس.
مثلًا، لقد اكتشف أن أداء جدول هاش
كان أسرع بنسبة 22% من أداء خريطة هاش،
بناءً على كيفية استخدامك للحاويات نفسها.
والفكرة هي كذلك.
هل سبق وقمت بتشخيص
فئات الحاويات التي تستخدمها في الكود؟
وهل أنت واثق من أنها تستخدم
الحاوية الأسرع على الإطلاق
لما يقوم به الكود في الواقع؟
مم، أجل، هذا ما كنت أفكر به.
لكن الشيء الجيد هو أنه
بإمكانك تحقيق شفافية في أداء
تلك الحاويات ببعض التشخيص اليدوي
لواجهات تمرير الرسائل في الأندرويد.
لذا لنرَ إن كان كود كريس يلتزم بفحصنا.
Hemos hablado sobre cómo tu código
puede ir lento por el tipo de hardware
que se ejecuta bajo él.
¿Recuerdas todo el problema
de ramificación de punto de flotación?
Bueno, eso no es problema
para el hardware de hoy.
Hay unos cuantos problemas
de lo que todavía tienes que preocuparte,
y es el rendimiento de los primitivos
en el lenguaje que estás usando.
Escoge un algoritmo fundamental,
como ordenación.
Hay muchas maneras en qué ordenar,
y algunas son mejores que otras,
según las circunstancias.
Por ejemplo, ordenación rápida
suele ser más rápida que la burbuja,
excepto cuando tienes menos de mil objetos
o realizas una búsqueda de estos
en una lista larga ordenada.
La mejor manera de hacer
esto es con una búsqueda binaria.
Pero es completamente diferente encontrar
objetos de un despliegue desordenado.
En lugar de comparar cada objeto
por el valor que estás buscando,
puedes usar un resumen criptográfico
para encontrarlo inmediatamente.
Todo esto son reglas básicas de estructura
de datos moderna e informática.
Y menos mal que los lenguajes modernos
como Java suministran estos contenedores
y algoritmos por ti, para que no tengas
que reescribir la función Murmur 3 Hash
o una ordenación rápida una y otra vez.
Pero déjame contarte algo.
En todos mis años de programación,
el único problema que corta el rendimiento
de tu proyecto consistentemente
tiene que ver con el rendimiento
de estos contenedores
de objetos del lenguaje.
Quiero decir, es impresionante, ¿no?
Java te suministra una implementación
de una clase de vector
que puedes presionar, explotar, añadir
y eliminar objetos como quieras.
Pero para conseguir esa flexibilidad tiene
que usar una estructura de lista enlazada
bajo el capó, que tiene un juega único
de características de rendimiento.
Mientras solo operes en la parte delantera
de la lista, es súper rápido,
pero si intentas insertar
o eliminar en otros lugares va a funcionar
con los peores tiempos posibles.
El punto es que solo porque los sistemas
subyacentes proporcionan
esos contenedores, no significa
que tengan buen rendimiento
con respecto a cómo tu programa
va a usarlos en realidad.
James Sutherland ha publicado una serie
de microbenchmarks sobre el rendimiento
de estructuras de datos específicas
proporcionadas por Java y descubrió
que hay algunas diferencias entre
rendimiento y funcionalidad
que la gente debe conocer.
Por ejemplo, descubrió que el rendimiento
de la tabla Hash,
era un 22% más rápida
que el rendimiento de HashMap,
dependiendo de cómo estés realmente usando
los contenedores en sí mismos.
El punto es este.
¿Has perfilado las clases
de contenedor que usas en el código?
¿Estás seguro de que estás usando
el contenedor más rápido
para lo que está haciendo tu código?
Ajá, eso es lo que pensaba.
Pero la buena noticia es que puedes ganar
visibilidad en el rendimiento
de estos contenedores con algunas MPIs
de perfilamiento útiles en Android.
Veamos si el código de Chris
resiste nuestro veredicto.
Nous avons parlé de la façon dont votre
code peut être lent
en raison du type de matériel
sous-jacent qui l'exécute,
vous savez ce problème des branchements
et des nombres flottants ?
Ça n'en est plus un
pour le matériel actuel,
mais il y a un tas de problèmes
dont on doit encore se soucier, à savoir :
l'exécution des primitives
dans le langage utilisé.
Prenons un algorithme fondamental,
par exemple le tri.
De nos jours, il existe
bien des façons de trier,
et certaines sont meilleures que d'autres,
en fonction des circonstances.
Par exemple, quickSort (tri rapide)
est généralement
plus rapide que Bubble Sort sauf si
on a moins de mille éléments
ou qu'on cherche des objets dans
une grande liste déjà triée.
En général, la meilleure méthode
est d'utiliser une recherche binaire,
mais c'est une autre histoire
si on cherche dans un tableau non trié.
Car au lieu de comparer chaque objet
avec la valeur recherchée,
on peut utiliser une fonction de hachage
pour la trouver sur-le-champ.
Ce ne sont que des règles de base en
informatique et en structure de données.
Et heureusement, les langages modernes
comme JAVA vous fournissent ces conteneurs
et autres algorithmes, ce qui évite
d'avoir à réécrire les fonctions
MurmurHash ou quickSort
chaque fois qu'on veut coder.
Mais j'ai une révélation à vous faire.
Dans toutes mes années de programmation,
le seul problème qui réduit toujours
la performance d'un projet
est l'exécution des objets que tel
ou tel conteneur de langage fournit.
Je veux dire, c'est génial, non ?
Java offre la mise en œuvre
d'une classe de vecteurs
qui peuvent pousser, afficher, ajouter
et supprimer des objets à loisir,
mais pour atteindre cette souplesse,
Java utilise une structure de listes liées
qui forment un ensemble unique
de caractéristiques de performance.
Tant qu'on n'utilise que les objets
prédéfinis d'une liste, c'est très rapide.
Mais si on veut insérer
ou supprimer des éléments précis,
il prendra par défaut
le pire type possible.
Au final, le fait que le système
sous-jacent fournisse ces conteneurs
n'implique pas
qu'ils seront performants
dans la façon dont votre programme
s'en servira concrètement.
James Sutherland a publié une série
de mini bancs de tests sur l'exécution
de structures de données spécifiques
fournies par le framework JAVA
et a découvert des différences
d'exécution vis-à-vis des fonctionnalités
que les gens devraient connaître.
Par exemple, il a constaté que
l'exécution de Hashtable
était environ 22% plus rapide
que l'exécution de HashMap
selon l'usage effectif
des conteneurs en eux-mêmes.
Voilà le principe :
avez-vous étudié les classes de conteneurs
utilisées dans le code ?
Êtes-vous convaincu qu'il s'agit vraiment
du conteneur le plus rapide
pour ce que votre code exécute ?
Hum, oui, je m'en doutais.
La bonne nouvelle, c'est qu'on peut
mieux visualiser les performances
de ces conteneurs avec des MPI
de profilage bien pratiques dans Android.
Voyons si le code de Chris
résistera à notre examen.
Kita telah membahas bagaimana kode Anda
dapat menjadi pelan karena jenis
perangkat keras yang menjalankannya,
ingat semua masalah
pencabangan floating point?
Baik, kebanyakan itu bukan masalah
bagi perangkat keras saat ini.
Ada beberapa masalah yang masih
perlu Anda khawatirkan, yaitu
kinerja sederhana pada
bahasa yang Anda gunakan.
Contohnya, algoritma dasar
seperti penyortiran.
Sekarang ada banyak
cara untuk menyortir,
dan beberapa di antaranya lebih baik
dari yang lain, tergantung kondisinya.
Misalnya, quicksort umumnya
lebih cepat dari bubble sort, kecuali
Anda memiliki kurang dari seribu elemen
atau mencari objek
di daftar sortiran yang besar.
Biasanya, cara terbaik untuk
melakukannya adalah pencarian biner.
Namun, yang sangat berbeda adalah mencari
objek di susunan yang tidak disortir.
Sekarang, daripada membandingkan nilai
setiap objek yang Anda cari,
Anda dapat menggunakan fungsi hash
untuk segera menemukannya.
Ini semua adalah kanon dasar ilmu
komputer modern dan struktur data.
Untungnya, bahasa modern seperti
Java menyuplai kontainer dan
algoritme untuk Anda, sehingga
Anda tidak perlu menulis ulang fungsi
Murmur 3 Hash atau
quicksort lagi dan lagi.
Tetapi, saya ungkapkan sesuatu di sini.
Dari pengalaman pemrograman saya,
satu masalah yang terus
mengganggu kinerja proyek
berkaitan dengan kinerja
objek kontainer dengan bahasa ini.
Maksud saya, itu luar biasa bukan?
Java menyediakan penerapan
kelas vektor mana yang
Anda dapat menekan, memindah, menambah,
dan menghapus objek yang cocok
namun, agar fleksibel, perlu digunakan
struktur daftar yang bertautan secara
mendasar, yang memiliki
karakteristik kinerja unik.
Selama Anda hanya beroperasi
di depan daftar, maka akan sangat cepat
Tetapi, jika Anda
ingin menyisipkan atau
menghapus di tempat lain, maka akan
menghasilkan waktu kemungkinan terburuk.
Intinya, hanya karena
sistem mendasar menyediakan
kontainer ini, bukan berarti
akan berkinerja tinggi
tergantung bagaimana program Anda
akan benar-benar menggunakannya.
James Sutherland menerbitkan serangkaian
patokan dasar untuk kinerja
struktur data tertentu yang disediakan
oleh kerangka kerja Java dan
ada perbedaan antara
kinerja dan fungsi
yang harus kita sadari.
Misalnya, dia menemukan
bahwa kinerja Hashtable
lebih cepat sekitar 22%
daripada kinerja HashMap,
tergantung bagaimana Anda
menggunakan kontainer itu sendiri.
Intinya seperti ini.
Sudahkan Anda memprofilkan kelas
yang Anda gunakan di kode?
Apakah Anda yakin mereka menggunakan
kontainer tercepat mutlak untuk
hal yang benar-benar
dikerjakan kode Anda?
Mmm, ya, itu pendapat saya.
Tapi, kabar baiknya Anda bisa memperoleh
visibilitas kinerja kontainer
ini dengan beberapa MPI
profil praktis di Android.
Jadi, mari kita lihat apakah kode Chris
valid untuk pemeriksaan kita.
先ほどは背後で実行中の
ハードウェアの種類によって
いかにコードが遅くなるかを
話しました
浮動小数点が枝分かれする
問題を覚えていますか
今回はそのことではありません
しかし気をつけるべき
問題があります
それは使用言語での Primitive の
パフォーマンスです
基本的なアルゴリズムである
並べ替えだと
今は多様な並べ替えが
できます
どう並べ替えるかも
状況によって異なります
例えば要素が1千未満または
大きな並べ替えリストから
検索する場合以外は一般的に
Quicksort は
Bubble Sort よりも速いです
一番だとされている
方法は二分探索です
しかし並べ替えしていない
Array の場合は違います
そこで探している数値で
オブジェクトを比較せず
代わりに Hash 機能を
使えばすぐです
これは現代のコンピュータ科学や
データ構造では基本になりました
お陰様で Java のような現代語が
このようなコンテナや
アルゴリズムを代わりにやるので
MurMur3 Hash や Quicksort を
何度も書き直す必要が
ありません
でもひとつ明かすとすると
プログラミングを
何年もやってきて
常にプロジェクトの
パフォーマンスを妨害するのは
言語付コンテナオブジェクトの
パフォーマンスにあります
凄いことではありますよ
Java は Vector クラスを
実行してくれるのですから
押下と押上そして追加や削除が
好きなようにできるのです
この柔軟性は表面下したにある
連結リストの構造からきています
これは変わった動作をします
作業がリストの表面上で
ある限りはとても速いです
しかし挿入や削除を
別の場所でやろうとすると
最悪な状態になります
表面下のシステムにコンテナが
あるからといって
作ったプログラムの仕様に
合わせている訳ではない
ということが重要な
ポイントです
ジェームス・サザーランド氏は
Java Framework による特定の
データ構造の動作における
マイクロベンチマークを
出版する際に動作と
機能性についての
注意点を発見しました
例えば Hashtabel は
コンテナを使い方しだいで
HashMap よりも
約 22% 速くなることを
発見しました
重要な点は
コードで使うコンテナクラスを
書いたかどうかです
自身のコードが実行する
動作に対して最速の
コンテナであると
言い切れますか
う~ん--そうですね
しかし便利な Android の
MPI を使えば
これらのコンテナの動作に
可視性が生まれます
ではクリス氏のコードは
これに対してどうでしょう
저번 시간에 프로그램의 속도가 느린 원인이
하드웨어일 수 있다는 점에 대해 얘기를 했었죠
부동 소수점 로직이 분기문 로직 이후에
위치해 발생한 문제 기억나시죠?
요즘 하드웨어에선 이런 문제가 발생하지 않는다고 생각하셔도 무방해요
하지만 한 가지 예외는 있어요
바로 여러분이 사용하는 언어의 기본 성능입니다
정렬같은 기본적인 알고리즘을 보세요
정렬 방법은 셀 수 없이 많죠
상황에 따라 몇 알고리즘이 다른 알고리즘보다 더 적합하고요
예를 들어 보통 퀵정렬은 버블정렬보다 더 좋지만
정렬하는 요소가 1천개 이하일 경우엔 그렇지 않아요
아니면 정렬된 리스트에서 객체를 찾을 땐
일반적으로는 이진 검색이 가장 효율적인 방법이에요
하지만 정렬되지 않은 리스트에서는 전혀 그렇지 않죠
각 객체의 값을 타겟 값과 비교하지 않고
해시 함수를 이용해 바로 찾을 수 있어요
방금 말씀드린 예시는 현대 컴퓨터과학과
자료구조에서 사용하는 기본적인 법칙이에요
다행히 자바 같이 최근 개발된 언어는
컨테이너와 알고리즘을 제공하기 때문에
여러분이 Murmur3 해시함수나 퀵정렬을
계속 작성하지 않아도 돼요
하지만 한 가지 말씀드릴게요
제가 몇년 동안 프로그래밍을 해보며 관찰한
모든 프로그램의 성능 문제는 부분적으로라도
언어가 제공하는 컨테이너 때문에 발생해요
물론 좋긴 하죠
자바가 제공하는 벡터 클래스로
여러분이 push, pop, add, remove를 사용할 수 있어요
하지만 그런 유연성을 위해서 자바는 연결 리스트 구조를 사용해야 해요
연결 리스트는 성능 측면에서 특이한 자료구조에요
연결 리스트의 앞부분에 작업을 하면 속도는 매우 빨라요
하지만 리스트의 중간에 insert나 remove를 하면
효율성은 최악이 됩니다
시스템이 아무리 편리한 컨테이너를 제공한다고 해도
여러분의 프로그램이 제공된 컨테이너를
효율적으로 활용할 거란 보장을 할 수 없어요
제임스 서덜랜드는 자바 프레임워크가 제공하는
자료구조에 대한 성능 벤치마크를 발표했는데요
벤치마크를 보면 성능과 기능성에 대한 괴리가 있다는 걸 알 수 있어요
예를 들어 Hashtable 성능이
HashMap 성능보다 22% 더 빠를 수도 있어요
컨테이너를 사용하는 방식에 따라 말이에요
중요한 건
여러분께서 사용하시는 컨테이너 클래스를 프로파일링 하셨는지에요
가장 효율적인 컨테이너를 사용 중이신지 확인하셨나요?
여러분의 코드가 실제로 수행하는 작업에 대해서 말이에요
흠 그럴 줄 알았어요
다행히도 안드로이드에서 컨테이너의
성능을 파악할 수 있는 MPI를 제공해요
그럼 크리스의 코드가 저희의 정밀 조사를 감당할 수 있을지 한번 보아요
Então, já falamos sobre como seu código
pode estar lento por causa do tipo de
hardware que está executando debaixo dele,
se lembra do problema do floating
point branching?
Bem, isso é principalmente um não-problema
para o hardware de hoje.
Ainda há um conjunto de problemas que você
precisa se preocupar, que é,
o desempenho das primitivas
na linguagem que você está usando.
Considere um algoritmo
fundamental tal como a ordenação.
Agora, há muitas
formas para ordenar,
e algumas são melhores que outras,
dependendo das circunstâncias.
Por exemplo, quicksort é geralmente
mais rápido do que o bubblesort exceto
quando você tem menos de mil elementos ou
faz pesquisa por
objetos numa lista ordenada.
Geralmente, a melhor forma de fazer
isto é com uma pesquisa binário.
Mas completamente diferente é encontrar
objetos num array não ordenado.
Agora, em vez de comparar cada objeto
para o valor que você procura,
você pode usar uma função hash
para o encontrar imediatamente.
Tudo isto é a base da moderna ciência
de computação e estruturas de dados.
E felizmente, as linguagens modernas como
o Java fornecem estes containers e
algoritmos em seu nome, para que
você não tenha de reescrever a função
Murmur 3 Hash function ou
o quicksort repetidamente.
Mas me deixe relevar algo aqui.
Em todos meus anos de programação,
o problema que consistentemente
afeta o desempenho de seu projeto
tem que ver com o desempenho destes
containers fornecidos pela linguagem.
Quer dizer, eles são ótimos, certo?
O Java fornece uma implementação
de classes de vetores que
você pode fazer push, pop, adicionar, e
remover objetos como você quiser, mas
para ter essa
flexibilidade, ele tem
de usar uma estrutura
de lista conectada por trás,
que tem um conjunto de
características de desempenho únicas.
Desde que você apenas esteja operando na
frente da lista, ele é super rápido.
Mas se você está tentando inserir ou
remover em outros lugares, ele vai
negligenciar para o pior tempo possível.
A questão é que só por que
o sistema subjacente fornece
estes containers, não significa
que eles vão ter bom desempenho
em relação a como seu programa
vai usar eles.
James Sutherland publicou uma série de
microbenchmarks sobre o desempenho de
estruturas de dados específicas
fornecidas pelo Java framework e
descobriu que há algumas diferenças
no desempenho versus funcionalidade
que as pessoas precisam conhecer.
Por exemplo, ele descobriu
que o desempenho de uma Hashtable
era cerca de 22% mais rápido
do que o desempenho de um HashMap,
dependendo de como você está
usando os próprios containers.
A questão é esta.
Você já criou o perfil das classes dos
containers que está usando em seu código?
Você está confiante que eles estão usando
o container mais rápido para
o que seu código está realmente fazendo?
Mm, sim, foi o que eu pensei.
Mas a boa notícia é que você pode ganhar
visibilidade quanto ao desempenho destes
containers com alguns úteis
MPIs de profiling no Android.
Então, vamos ver se o código do Chris
está à altura do nosso escrutínio.
Мы уже обсудили, что медленное
исполнение кода может быть вызвано
особенностями аппаратного обеспечения.
Помните проблему с плавающей запятой
и условным переходом?
Для современной техники она
уже не так актуальна.
Но есть комплекс проблем, на которые
вам всё ещё стоит обращать внимание.
Речь идёт о быстродействии примитивов
в том языке, на котором вы пишете.
Возьмём фундаментальный
алгоритм, например упорядочивание.
Существует множество
способов упорядочивания.
В зависимости от обстоятельств,
одни могут быть лучше других.
Например, обычно Quicksort
работает быстрее, чем Bubble Sort,
кроме случаев,
когда у вас менее 1000 элементов.
Или возьмём поиск
по большому упорядоченному списку.
Обычно его лучше проводить
с помощью Binary Search.
Но поиск объектов в неупорядоченном
массиве — это совсем другая история.
Вместо того, чтобы сравнивать
каждый объект с искомым значением,
вы можете использовать функцию Hash
и получить результат мгновенно.
Это всё базовые правила современной
информатики и структур данных.
К счастью, современные языки,
такие как Java, содержат уже готовые
контейнеры и алгоритмы, и вам не нужно
писать с нуля снова и снова
функции MurmurHash3 или Quicksort.
Но нужно отметить один момент.
Во всём моём опыте программирования
одна проблема постоянно сказывается
на быстродействии проекта:
это быстродействие контейнеров,
содержащихся в языке.
Это же так здорово, да?
Java предоставляет вам программную
реализацию класса vector, чтобы
вы могли двигать, выталкивать, добавлять
и удалять объекты по своему усмотрению.
Но такая гибкость обеспечена за счет
скрытой структуры связанных списков,
которая обладает уникальными
характеристиками быстродействия.
Пока вы обращаетесь только к верхней
части списка, работа идёт очень быстро.
Но попытка вставить
или удалить объект в других местах
сделает время задержки максимальным.
Главный вывод здесь такой:
наличие этих контейнеров в базовой системе
ещё не гарантирует
быстроту их действия
в контексте вашей программы.
Джеймс Сазерленд опубликовал результаты
серии тестов производительности,
проведённых на структурах данных,
которые предоставляет Java.
Он обнаружил некоторые расхождения между
производительностью и функциональностью,
на которые необходимо обращать внимание.
К примеру, он заметил
что метод Hashtable
может быть примерно на 22% быстрее,
чем метод HashMap,
в зависимости от способа
использования контейнеров.
К чему я веду?
Вы составили профиль тех контейнеров,
которые используете?
Вы уверены, что выбрали
самые быстрые контейнеры
подходящие для вашего кода?
Ну да. Так я и думал.
Хорошая новость в том, что вы можете
увидеть быстродействие этих контейнеров
с помощью удобных
MPI для профилирования на Android.
Давайте посмотрим,
выдержит ли критику код Криса.
Kodunuzun, donanım nedeniyle
yavaş çalışabileceği
hakkında konuştuk,
kayan nokta dallanma meselesi
sorununu hatırlıyor musunuz?
Pekala, bu, günümüzdeki donanımlar
için çoğunlukla sorun değildirç
Fakat hala endişe duymanız gereken
bir konu var:
kullandığınız dildeki temellerin
performansı.
Bir temel algoritmayı, örneğin sıralamayı
ele alalım.
Sıralama yapmanın bir çok
yolu vardır,
koşullara bağlı olarak,
bazıları daha iyidir.
Örneğin, çabuk sıralama genel olarak
kabarcık sıralamadan daha hızlıdır, bin
öğeden daha azının elinizde olması ya da
geniş bir sıralamada, nesneler
için arama yapıyor olmanız haricinde.
Genel olarak, bunu yapmak
için en iyi yol ikili aramadır.
Fakat sıralanmamış bir dizilişte
bir nesne bulmak bütünüyle farklıdır.
Nesneyi bulmak için, her nesnesiyi
aradığınız değer ile karşılaştırmak yerine,
özet fonksiyonunu
kullanabilirsiniz.
Bu, yüm modern bilgisayar biliminin
ve veri yapılarının temel düzenidir.
Java gibi modern diller,
bu kapsayıcıları ve algoritmaları
sizin adınıza sağlar, böylece Murmur
3 Hash fonkiyonunu ve çabuk sıralamayı
tekrar tekrar yazmanıza
gerek kalmaz.
Lütfen birşeyi ortaya
koymama izin verin.
Programlamayla geçirdiğim
yıllar boyunca,
projelerin performansını sürekli olarak
etkileyen problemin, bu dillerin
sağladığı kapsayıcı nesnelerinin
performansıyla ilişkili olduğunu gördüm.
Bu müthiş, değil mi?
Java, saladığı vektör sınıfıyla, nasıl
uygun görüyorsanız o şekilde, nesneleri
ekleme ve çıkarma imkanı sağlar,
fakat bu esnekliği sağlamak için,
özgün performans nitelikleri
olan başlık altındaki
bağlı liste yapısını
kullanır.
Listenin baş kısmında yürütme yaptığınız
sürece, çok hızlıdır.
Fakat eğer diğer yerlerde ekleme ya da
çıkarma yaparsanız, olabilecek en kötü
zamanda varsayılana dönecektir.
Mesele şudur ki, temel sistemin
bu kapsayıcıları sağlaması,
bu kapsayıcıların, programınızla
uygun biçimde
çalışacağı anlamına gelmez.
James Sutherland, Java çerçevesinin
sağladığı spesifik veri yapılarının
performansı üzerine bir dizi
performans değerlendirmesi yayınladı
ve insanların farkında olması gereken,
performans ve işlevsellik arasında
bir dizi farklılık tesipt etti.
Örneğin, komut tablosunun
performansının
KomutHaritasından,
kapsayıcıları nasıl kullandığınıza
bağlı olarak, %22 daha hızlı
olduğunu tesipt etti.
İşte mesele bu.
Kodunuzda kulladığınız kapsayıcı
sınıflarının profilini çıkardınız mı?
Bunların, kodunuzun yaptığı şey
için en hızlı kapsayıcıyı
kullandığından emin misiniz?
Hımm, Evet, düşündüğüm şey buydu.
İyi haber şu ki, bu kapsayıcıların
performansına, Android içindeki
MPI'ların profillerini çıkararak,
görünürlük kazandırabilirsiniz.
Şimdi Chris'in kodunun sınamamızdan
geçip geçemeyeceğine bakalım.
Chúng ta đã nói về mã của bạn
có thể bị chậm thế nào
vì loại phần cứng thực thi bên dưới,
bạn có nhớ việc chia nhánh
dấu chấm động gây ra vấn đề?
Đó không phải là vấn đề
với phần cứng.
Có một loạt vấn đề mà bạn
vẫn cần phải lo lắng,
đó là hiệu suất của các từ gốc
trong ngôn ngữ mà bạn đang sử dụng.
Dùng thuật toán cơ bản
như phân loại.
Bây giờ có rất nhiều
cách để sắp xếp,
và một số cách tốt hơn các cách khác,
tùy thuộc vào hoàn cảnh.
Ví dụ, quicksort thường
nhanh hơn bubble sort
trừ khi bạn có một ít hơn một nghìn yếu tố
hoặc tìm kiếm các đối tượng
trong một danh sách sắp xếp lớn.
Cách tốt nhất để làm
điều này là bằng tìm kiếm nhị phân.
Nhưng khác hoàn toàn là tìm kiếm
đối tượng trong mảng không sắp xếp.
Thay vì so sánh đối tượng
cho các giá trị mà bạn tìm kiếm,
bạn có thể dùng một hàm harsh
để tìm đối tượng ngay.
Đó là tiêu chuẩn cơ bản của khoa học
máy tính hiện đại và cấu trúc dữ liệu.
Và may mắn là, ngôn ngữ hiện đại
như Java cung cấp các bộ chứa
và các thuật toán thay bạn, vì vậy
không cần viết lại hàm Murmur3 hash.
hoặc quicksort hết lần này đến lần khác.
Nhưng hãy để tôi cho bạn biết.
Nhiều năm tôi làm về lập trình,
một vấn đề luôn ảnh hưởng đến
hiệu suất dự án của bạn
có liên quan đến hiệu suất
của đối tượng bộ chứa ngôn ngữ được cấp.
Điều đó tuyệt vời, phải không?
Java cung cấp cho bạn
thực hiện một lớp véc tơ
mà bạn có thể đẩy, hiển thị, thêm và
loại bỏ đối tượng nếu thấy phù hợp,
nhưng để linh hoạt, bạn phải dùng
cấu trúc danh sách liên kết dưới mũ,
trong đó có một chuỗi
đặc tính hiệu suất duy nhất.
Miễn là bạn chỉ hoạt động trên
mặt trước của danh sách, nó sẽ rất nhanh.
Nếu bạn cố chèn hoặc xóa những nơi khác,
nó sẽ mặc định thời gian
tồi tệ nhất có thể.
Điểm đáng nói là chỉ vì
hệ thống cơ bản cung cấp bộ chứa,
không có nghĩa
là chúng làm việc với hiệu suất
tương ứng với mức mà chương trình của bạn
thực sự sẽ sử dụng chúng.
James Sutherland công bố loạt tiêu chuẩn
đánh giá siêu nhỏ về hiệu suất
của cấu trúc dữ liệu cụ thể được cung cấp
bởi khung làm việc Java
và thấy rằng có một số khác biệt
trong hiệu suất so với chức năng
mà mọi người cần biết.
Ví dụ, ông thấy rằng hiệu suất Hashtable
nhanh hơn khoảng 22%
so với hiệu suất HashMap,
tùy thuộc vào cách bạn thực sự
sử dụng bản thân các bộ chứa.
Vấn đề nằm ở chỗ.
Bạn tóm lược lớp bộ chứa
đang sử dụng trong mã chưa?
Bạn có tự tin rằng chúng đang sử dụng
bộ chứa nhanh nhất
cho những gì mã của bạn thực sự đang làm?
Vâng, đó là những gì tôi nghĩ.
Nhưng tin tốt là bạn có thể biết
hiệu suất của các bộ chứa
với một số MPI tóm lược
tiện dụng trong Android.
Xem mã của Chris có qua
bài kiểm tra không.
前面我们讲过,
一些类型的硬件可能会造成程序执行速度较慢。
还记得那个浮点分支问题吗?
对于今天的硬件来说,这已经不是问题。
但是有一些问题还是需要引起注意。
比如说,你所使用的编程语言的基本元素的效率
以排序等基本算法为例,
现在,有很多的排序算法。
对于不同的情况,它们各有优劣。
例如, 当元素数量少于一千
或在大型已排序列表中寻找一个对象时,
快速排序法通常比起泡排序法更快。
一般情况下,最好的方法是二分查找算法。
但是,当在未排数组中寻找对象时情况变得完全不同,
不同于比较每一个对象以查找你想要的值。
你可以使用一个哈希函数来立即找到它。
这是现代计算机科学和数据结构方面的基本知识。
幸运的是,现代编程语言像Java等,
为你提供这些容器和算法,
因此你不再需要自己反复地编写Murmur3哈希函数
和快速排序算法.
但是你需要知道另外一些事情,
在我多年的编程生涯中,
一个经常会影响项目性能的问题
是由于这些语言提供的容器对象的性能所引起的。
这听起来不可思议,是吧。
Java提供一个失量类的实现。
你可以任意推入、弹出、添加和取消对象。
为了获得这种灵活性,
它在内部使用链式列表结构。
这种结构具有一系列独特的性能特性,
在你操作这种列表时,它的速度超级快。
但是,当你在其他位置进行插入或删除时,
它会消耗大量的时间。
我要说的是,
底层系统提供这些的容器并不会考虑,
你的程序将会如何实际使用它们。
James Sutherland发表了一系列的基准测试报告。
阐述Java Framework提供的特定数据结构的性能。
他认为,我们需要注意性能与功能之间的一些差异。
例如,他发现Hashtable比HashMap大约快22%,
具体视你如何使用这些容器而有所不同。
我们需要思考的是,
你是否曾经分析过你在代码中使用的容器类。
你是否坚信,
你在代码中使用的容器的实际运行速度绝对是最快的。
是的,这就我在考虑的事情。
一个好消息是,
你可以使用Android 中的剖析MPI来剖析这些容器的性能。
让我们来看Chris的代码是否经得起我们的检验。
到目前為止我們已經談論了
你的代碼會如何
因為運行的硬體而變慢
還記得那個浮點分支的問題嗎
雖然這對於現今的硬體都幾乎不是個問題
但還是有一組問題你需要擔心
那就是
你正在使用的語言中原語的效能
以一個基礎的演算法
比如排序做說明
有很多種方式可以進行排序的動作
在某些情況下
某些會比另外一些更好
舉例來說 quicksort在一般情況下會比
bubble sort更快
但若你有少於一千個元素則不然
或在一個大的排序列表中搜尋時
通常情況下 最好的方法是用二進制搜尋
但在未排序的數組中尋找物件
則完全不同
在這裡 比起比較每個物件
來尋找你要的值
利用哈希函數你可以馬上找到
這些都是現代電腦科學
與數據結構的基本教規
還有令人慶幸的是 如Java等現代語言
都幫你支援這些容器以及演算法
所以你就不需要一遍又一遍的
一直重複寫Murmur
3 哈希函數或quicksort
但讓我也在這裡透露一件事
在我多年的編碼經驗中
一個持續吃掉你的項目的效能
就是與那些語言提供容器物件的
效能有關
這很棒 不是嗎
Java提供你一個
可以讓你覺得在適當的地方
以推 彈 加入和刪除等矢量類的實現
但為了要能夠實現那種靈活性
在引擎蓋下它必須用一個連結的列表結構
且它具有一套獨特的效能特性
只要你在上列表上的前端上作業
它就會超極快
但若你嘗試在其他地方加入或移除
它會預設為最差的時間
重點是就算這些底層系統提供了容器
這也不代表著你的程序
會以高效能的方式使用它們
James Sutherland在Java框架內所提供的
特定數據結構的效能上制定了
一系列的微基準
並發現了人們應該要知道效能與
功能性有著差異
舉例來說
他發現了Hashtable效能
要比HashMap效能快上22%
與你如何使用容器有關
重點是
你有分析了你使用在
你的代碼中的容器類了嗎
你確定你的代碼實際在做的事情
是使用了最快的容器嗎
對 我也不這麼認為
但好消息是你可以用安卓中好用的分析MPI
來窺探這些容器的效能
我們一起來看看克里斯的編碼能
不能通過我們的檢測