|
Java форум JavaTalks
форум программистов
|
|
|
|
| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
alexey : 213
Новичок
Откуда: Спб
|
 Ноя 10, 2011 0:32 |
 |
|
ух, я смотрю ты потрудился )
я писал сверху измененный метод main, им удобно проверять - там 100 потоков (а не два) пихают одновременно в мапу случайные числа. да еще и не один раз, а в бесконечном цикле. а в конце выводят содержимое мапы, должно быть 10.
и твоя мапа этот тест не прошла
| Код: |
Result: 4 - 10
map = {15=a, 65=a, 97=a, 98=a}
Result: 3 - 10
map = {83=a, 92=a, 93=a}
Result: 7 - 10
map = {8=a, 13=a, 83=a, 87=a, 95=a, 96=a, 99=a}
Result: 6 - 10
map = {18=a, 49=a, 90=a, 97=a, 98=a, 99=a}
Result: 6 - 10
map = {33=a, 56=a, 96=a, 97=a, 98=a, 99=a}
Result: 6 - 10
map = {3=a, 60=a, 93=a, 94=a, 98=a, 99=a}
|
Проблема та же, что и была, и которую не убрать без синхронизации - между изменением счетчика и непосредственным удалением/добавлением элемента может влезть другой поток, который застанет счетчик уже измененным, а мапу еще не измененную и сделает неправильные выводы из-за этого.
_________________
 |
|
|
|
 |
dok : 71
Новичок
|
| Ноя 10, 2011 8:42 |
| |
|
| Аааа, у нас тесты не эквивалентные. У меня ключи более-менее уникальные, а у тебя повторяющиеся. Да, моё решение на это конечно не расчитано. Вечерком попробую проенхансить. |
|
|
|
|
abch-98-ru : 38
Новичок
|
| Ноя 10, 2011 11:31 |
| |
|
| abch-98-ru писал(а): |
| alexey писал(а): |
| нужно, чтобы не больше, но и лишнего не удалял. Т.е. если я запихал в мапу 100 разных значений, а мапа максимального размера 10, то я ожидаю в конце увидеть 10, а не 8 или 9. |
не, без критической секции или какого-нить stm, это никак имхо. 
на два поля атомарных инструкций не знаю  |
хотя если подумать, то проапдейтить решение можно.
| Код: |
static class MyMap<K, V> implements Map<K, V> {
public static final int MAX_SIZE = 10;
private AtomicInteger size = new AtomicInteger();
private ConcurrentSkipListMap<K, Entry<V>> forwardMap = new ConcurrentSkipListMap<>();
@Override
public int size() {
return forwardMap.size();
}
class Entry<V> {
V value;
AtomicBoolean inUse = new AtomicBoolean();
Entry(V value) {
this.value = value;
}
@Override
public String toString() {
return "Entry{" +
"value=" + value +
", inUse=" + inUse +
'}';
}
}
@Override
public V put(K key, V value) {
// insert entry
Entry<V> newEntry = new Entry<>(value);
Entry<V> oldValue = forwardMap.putIfAbsent(key, newEntry);
while (oldValue != null) { // while there are something in cache.
if (oldValue.inUse.compareAndSet(false, true)) {
forwardMap.put(key, newEntry);
return oldValue.value;
} else {
Thread.yield();
oldValue = forwardMap.putIfAbsent(key, newEntry);
}
}
// for new entries update size.
updateSize();
return null;
}
private void updateSize() {
int currSize = size.get();
while (currSize < MAX_SIZE) {
if (currSize + 1 <= MAX_SIZE && size.compareAndSet(currSize, currSize + 1)) {
return;
} else {
currSize = size.get();
}
}
if (currSize == MAX_SIZE) {
forwardMap.pollFirstEntry();
}
}
/*the other methods*/
}
|
|
|
|
|
|
dok : 71
Новичок
|
| Ноя 11, 2011 23:31 |
| |
|
Ну вроде починил. Счётчик в процессе работы конечно может отличаться от того, что будет после завершения метода, потому что size в процессе put() сначала увеличивается, потом уменьшается обратно в случае чего. Но в итоге после всех put/remove размер вроде оказывается expected.
Для проверки я сделал 2 цикла - put/remove и потом просто put, чтобы проверить, что в итоге размер будет 10.
| Код: |
package test;
import java.util.NoSuchElementException;
import java.util.Random;
import java.util.Set;
import java.util.concurrent.*;
import java.util.concurrent.atomic.AtomicInteger;
public class Test2
{
public static final AtomicInteger put = new AtomicInteger();
public static final AtomicInteger removed = new AtomicInteger();
public static void main(String[] args) throws Exception
{
while (true)
{
final Random random = new Random();
final MyMap map = new MyMap();
ExecutorService service = Executors.newFixedThreadPool(10);
for (int i = 0; i < 100000; i++)
{
final int j = i;
service.submit(new Runnable()
{
public void run()
{
if (j % 4 == 0)
{
map.remove(random.nextInt(100));
}
else
{
map.put(random.nextInt(100), "a");
}
}
});
}
service.shutdown();
service.awaitTermination(1000, TimeUnit.SECONDS);
service = Executors.newFixedThreadPool(10);
for (int i = 0; i < 100; i++)
{
service.submit(new Runnable()
{
public void run()
{
map.put(random.nextInt(100), "a");
}
});
}
service.shutdown();
service.awaitTermination(1000, TimeUnit.SECONDS);
System.out.println("Result: " + map.size() + " - " + map.mySize());
System.out.println("put: " + put.get() + " - remove: " + removed.get());
System.out.println("map = " + map);
System.exit(0);
}
}
static class MyMap extends ConcurrentSkipListMap
{
public static final int MAX_SIZE = 10;
private AtomicInteger size = new AtomicInteger();
@Override
public Object put(Object key, Object value)
{
put.incrementAndGet();
int newSize = size.incrementAndGet();
Object previousValue = super.put(key, value);
if (previousValue == null)
{
if (newSize > MAX_SIZE)
{
removeSingleElement();
}
}
else
{
size.decrementAndGet();
}
return previousValue;
}
private void removeSingleElement()
{
while (true)
{
Object firstKey;
try
{
firstKey = firstKey();
if (remove(firstKey) != null)
{
//todo handle case when map is already empty
removed.incrementAndGet();
return;
}
}
catch (NoSuchElementException e)
{
//ok
}
}
}
public int mySize()
{
return size.get();
}
@Override
public Object remove(Object key)
{
Object removed = super.remove(key);
if (removed != null)
{
size.decrementAndGet();
}
return removed;
}
}
}
|
|
|
|
|
|
alexey : 213
Новичок
Откуда: Спб
|
| Ноя 13, 2011 21:30 |
| |
|
увы, оба варианта не прошли теста.
| Код: |
map = {6=a, 7=a, 18=a, 47=a, 48=a, 52=a, 53=a, 56=a, 60=a, 73=a}
Result: 9 - 9
map = {0=a, 4=a, 5=a, 22=a, 27=a, 31=a, 44=a, 57=a, 94=a}
Result: 10 - 10
map = {2=a, 5=a, 6=a, 8=a, 28=a, 30=a, 31=a, 53=a, 69=a, 84=a}
Result: 10 - 10
map = {3=a, 4=a, 8=a, 53=a, 68=a, 80=a, 82=a, 87=a, 98=a, 99=a}
|
это последний с extends ConcurrentSkipList
обычный тест
| Код: |
public static void main(String[] args) throws Exception {
while (true) {
final Random random = new Random();
final MyMap map = new MyMap();
ExecutorService service = Executors.newFixedThreadPool(10);
for (int i = 0; i < 10; i++) {
service.submit(new Runnable() {
public void run() {
int put = random.nextInt(100);
map.put(put, "a");
}
});
}
Thread.sleep(1000);
System.out.println("Result: " + map.size() + " - " + map.mySize());
System.out.println("map = " + map);
}
}
|
[/code]
_________________
|
|
|
|
|
abch-98-ru : 38
Новичок
|
| Ноя 13, 2011 23:55 |
| |
|
| alexey писал(а): |
| увы, оба варианта не прошли теста. |
коллега, у вас неправильный тест
из-за вашего random-а вы таки можете не получить 10 с какой-то вероятностью.
так как ваш тест не работает, то предлагаю свои:
тест1. заменить ваш цикл на
| Код: |
for (int i = 0; i < 10; i++) {
final int finalI = i;
service.submit(new Runnable() {
public void run() {
map.put(finalI, finalI);
}
});
}
|
тест2.
чтобы проверить как ведёт себя при одинаковых ключах.
кста,
| Код: |
static class MyMap<K, V> implements Map<K, V> {
private final int maxSize;
private final AtomicInteger size = new AtomicInteger();
private final ConcurrentSkipListMap<K, V> forwardMap = new ConcurrentSkipListMap<>();
public MyMap(int maxSize) {
this.maxSize = maxSize;
}
@Override
public V put(K key, V value) {
// insert entry
V result = forwardMap.put(key, value);
if (result == null) {
updateSize();
}
return result;
}
private void updateSize() {
int currSize = size.get();
while (currSize < maxSize) {
if (currSize + 1 <= maxSize&& size.compareAndSet(currSize, currSize + 1)) {
return;
} else {
currSize = size.get();
}
}
if (currSize == maxSize) {
forwardMap.pollFirstEntry();
}
}
/*other*/
}
|
ещё проще и в конце теста всё будет ок.
в середине может быть больше, понятно-на-какое-число.
если хочется, чтобы было наоборот меньше, вы уж сами. имхо, там поинтересней будет ) |
|
|
|
|
alexey : 213
Новичок
Откуда: Спб
|
| Ноя 14, 2011 17:11 |
| |
|
а, туплю, действительно, плохой тест...
сейчас посмотрю повнимательнее на ваш код последний, потестирую, спасибо.
_________________
|
|
|
|
|
|
|
Страница 2 из 2
На страницу Пред. 1, 2 |
Список форумов
-> Нити и процессы |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
|
|
